Recursion properties, Fibonacci, TOH algorithm

Properties of recursion

1. A recursive function calls itself, directly or indirectly.
2. It has a base case (stopping condition) whose answer is known without further calls.
3. Each recursive call works on a smaller or simpler version of the problem and moves toward the base case.
4. Every call has its own parameters, local variables and return address, stored on the stack.
5. The result is built while returning (unwinding) from the calls.
6. Without a reachable base case the recursion is infinite and ends in stack overflow.

Why recursive Fibonacci is not preferred

fib(n) = fib(n-1) + fib(n-2), fib(0) = 0, fib(1) = 1. The same sub-problems are solved again and again: in fib(5), fib(3) is computed twice and fib(2) three times. The number of calls grows exponentially (fib(5): 15 calls, fib(30): 2,692,537 calls, counted by program), time is O(2ⁿ), and stack depth is n. An iterative loop gives the answer in n steps with constant memory.

TOH algorithm

TOH(n, from, to, aux):

1. If n = 1, move disk 1 from from to to and return.
2. TOH(n-1, from, aux, to).
3. Move disk n from from to to.
4. TOH(n-1, aux, to, from).

Solution for 3 disks: TOH(3, A, C, B)

Total 2³ − 1 = 7 moves.