title: Tree Recursive Fibonacci Algorithm Requires Linear Space?
body: <p>I know that the Fibonacci series grows exponentially, therefore a recursive algorithm has a required number of steps that grow exponentially, however SICP v2 says that a tree recursive Fibonacci algorithm requires linear space because we only need to keep track of the nodes above us in the tree. </p>
  
  <p>I understand that the required number of steps grows linear with Fib(n) but I would also assume that because the tree is expanding exponentially, the memory required in this event would need to be exponential as well. Can someone explain why the memory required only expands linearly to N, and not exponentially?</p>