Consider this definition of Fibonacci numbers:
fib( 0, 1 ). fib( 1, 1 ). fib( N, F ) :- N1 is N - 1, N2 is N - 2, fib( N1, F1 ), fib( N2, F2 ), F is F1 + F2.
fib is called, it will work right down to
This means that it wastes its time in repeatedly recalculating results.