Tree recursion is another common computational pattern. An often used example in this direction is computing the Fibonacci numbers, in which each number is the sum of the proceeding two:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
Let’s see a recursive function to computing Fibonacci numbers, that will result in a tree recursive process:
Visualizing the process
Similary to what we did before we can use the sobstitution model to visualize the process of computing fib(5) :
While this function show us a typical tree recursion process is a terrible way to compute Fibonacci numbers, as it does a lot of rendundant calulculations. The process uses a number of steps that grows exponentially with the input. The space complexity on the other side only grows linearly because we need to keep track only of which nodes are above us in the tree at any point in the computation. In other words the space required is proportional to the maximum depth of the tree.
If you read my post on DepthFirst and breadthFirst tree walking you may notice that a Depth-First Search algorithm rely on a Stack datastructure. I’ll leave it to the reader to find any parallelism with the call stack used by the interpreter to keep track of the deferred operations and why the space required in a tree recursion is proportional to the maximum depth of the tree…
We can also define a recursive function to compute the Fibonacci numbers that will instead generate a linear iterative process (as in ES6, thanks to its tail-call optimization):
Now that we saw different recursive processes we may start noticing some pattern emerging in how we define the recursive function responsibles for such processes.