This part introduces tree recursion, a form of recursion that occurs when a function calls itself more than once in a path. We then introduce dynamic programming, a class of algorithms to tackle certain types of tree recursive problems.
Some recursive functions call themselves more than once. Consider the function to calculate the nth term of a fibonacci series (also known as virahanka series):
def fibonacci(n): if n == 0: return 0 if n == 1: return 1 return fibonacci(n - 2) + fibonacci(n - 1)
In order to calculate
fibonacci(4), we need to calculate
fibonacci(3). For each call, there are two more recursive calls. This proceeds until n becomes 0 or 1, which are the terminating points of the recursion. We see that execution follows a tree form like this:
fibonacci(4) +------------------------------ | | fibonacci(2) fibonacci(3) +----------------- +--------------- | | | | fibonacci(0) fibonacci(1) fibonacci(1) fibonacci(2) +----------- | | fibonacci(0) fibonacci(1)
Each node has two children, one for each recursive call. A function with 'n' recursive calls will have 'n' children at each node. Since program execution follows a tree like structure, we call this form of recursion tree recursion
Is there any way to convert tree recursion to iteration?
The short answer is no. There is no general algorithm to convert tree recursion to iteration. However, specialised algorithms do exists for certain problems. These algorithms (if they exist) are usually specific to each problem.
And it just so happens that our fibonacci algorithm falls into a class of tree recursive problems that can be converted to iteration using a technique called dynamic programming!
Look at the execution pattern for
fibonacci(4) again. Notice how
fibonacci(2) is calculated twice: Once in the computation of
fibonacci(4) and once again in the computation of
fibonacci(1) is computed thrice!
What if we could save the values of previous fibonacci terms when they are first computed and reuse the values later on without having to compute them again? This optimisation is the cornerstone of dynamic programming.
Here is how we can proceed:
- Store the initial values of
fibonacci(1). The saved value of
fibonacci(0)is now no longer required, so we can discard it.
- In general, compute
fibonacci(n + 1)from the saved values of
fibonacci(n - 1)and
fibonacci(n). Discard the value of
fibonacci(n - 1).
- Repeat step 3 until we have computed the desired term
Look at the execution tree again. Notice how we start the computation from the leaf nodes of the tree and work our way up the tree computing each node, until we reach the root, which is the value we desire.
Here is the implementation using iteration:
def fibonacci(n): out = 0 next = 1 for _ in range(1, n + 1): out, next = next, out + next return out
We have just used dynamic programming to convert a tree recursive algorithm into an iterative algorithm. The basic idea of dynamic programming is to look at the execution tree, identify repeated computations and perform the calculations 'bottom-up' from leaf to root. At each step, the computed values of the subproblems are stored to be reused later.
Dynamic programming cannot be used on every problem. Some problems can be converted to iteration using other methods, and some problems cannot be converted to iteration at all. Nevertheless, dynamic programming works on a large class of problems, and it is a useful tool to have in the toolbox