Tree Recursion

In the article, TDD Cycle Red Green Refactor, the solution was driven by tests. In this article, we will learn a bit more about Fibonacci sequence.

Tree recursion is a common pattern of computation. In Fibonacci sequence, each number is the sum of the preceding two.

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

This sequence can be defined by the rule:

Fib(n) = 0 if n = 0
         = 1 if n = 1
         = Fib(n - 1) + Fib(n - 2) otherwise

We can translate this definition into a recursive procedure for computing Fibonacci sequence. In Scheme:

(define (fib n)
  (cond ((= n 0) 0)
             ((= n 1) 1)
             (else (+ (fib(- n 1))
                           (fib(- n 2))))))

If you draw the execution of the program, for instance for n = 5, you will see a tree structure. The resulting tree-recursive process is an example of tree recursion. The process uses a number of steps that grows exponentially with the input. The space required grows only linearly with the input, because we need to keep track of only which nodes are above us in the tree at any point in the computation. In general, the number of steps required by a tree-recursive process will be proportional to the number of nodes in the tree, while the space required will be proportional to the maximum depth of the tree. The Ruby equivalent solution:

def fibonacci(n)
  return 0 if n == 0
  return 1 if n == 1
  fibonacci(n - 1) + fibonacci(n - 2)
end

0.upto(10) {|n| p fibonacci(n) }

You can see how it maps directly from the Fibonacci rules to code. The first two rules are expressed as base conditions. The third rule is expressed as two recursive calls that reduces the input by specified amount.

Reference

Structure and Interpretation of Computer Programs Gerald Jay Sussman and Hal Abelson


Related Articles


Ace the Technical Interview

  • Easily find the gaps in your knowledge
  • Get customized lessons based on where you are
  • Take consistent action everyday
  • Builtin accountability to keep you on track
  • You will solve bigger problems over time
  • Get the job of your dreams

Take the 30 Day Coding Skills Challenge

Gain confidence to attend the interview

No spam ever. Unsubscribe anytime.