Explain, please, why with an increase in the argument passed to the tree-recursive procedure , the memory requirement grows linearly ? (The sicp explains: "... memory requirements grow linearly, because at each point of the calculation we only need to memorize the vertices that are higher than us in the tree," but still could not understand why).

  • As far as I understand, we are talking about the fact that at a particular point in time the process is only in one branch, and therefore the maximum memory requirement depends on the length of this branch. - etki

1 answer 1

Found the answer, I think many who do not know, it will be clear:

Single (linear) recursion forms a single-width deep call stack and quickly populates the stack. Program runtime until stack overflow is negligible.

The double (tree) recursion, on the contrary, forms a wide stack of calls, the width of which grows exponentially. The number of instances of the recursive function grows like an avalanche. This leads to a sharp slowdown in the program. At the same time, the stack size of the program grows linearly with increasing stack depth.

So a call to the Fib (50) function (calculation of the 50th Fibonacci number) will entail a call of 2 ^ 50 = 1 Pentabyte of Fib instances, while the program stack will contain as much as 50 · (2 ​​+ 4) = 300 bytes.