Recursive versus non-recursive
- Every recursive program has an equivalent non-recursive program.
- Some problems that are simple to solve with recursion are more difficult to solve without recursion. For example, any non-recursive solution for the Towers of Hanoi is complicated and messy.
- For some problems, the use of recursion is not natural or not efficient.
- A simple non-recursive version is often more efficient than a recursive one. For example, finding the minimum or maximum in an unsorted sequence or computing the sum of n numbers should not be done using recursion.
Why recursive programs can be slow
- When a recursive program re-computes quantities that already have been computed by earlier calls, recursion typically becomes very expensive!
- We showed three functions computing the n-th Fibonacci number. Function calcFibRecur in file Fibonacci.py uses the definition f(n) = f(n-1) + f(n-2). When computing f(29), function calcFibRecur is about 18000 times slower than the iterative version or the recursive version avoiding recomputation.
For more advanced students discuss system overhead in the form of a needed stack. A call stack is a data structure used by the program to store information about the active subroutines in a program. The stack is used so that the program can keep track of where a subroutine should return control to once it finishes executing.
