Recursive Processes

Hey guys,

There is a section at this link (http://mitpress.mit.edu/sicp/full-t...tml#%_sec_1.2.2) that says (so you can find it):

"On the other hand, the space required grows only linearly with the input, because we need keep track only of which nodes are above us in the tree at any point in the computation."

I can't seem to understand why the space required is not proportional to the number of nodes in the tree. From what I understand, every node that is not a leaf needs to remember the addition so it can be executed later, so barring the Fib(n+1) leaf nodes, every other node should require memory to store the addition operator.

Why would the addition operator need to be stored? Maybe you should explain what you think is going on.

Each addition is deferred until all the Fib(n) to Fib(1) have been calculated, and then everything can be summed because the base case finally gives a number. From what I understand, each deferred addition takes up space in memory, and each node (beside leaf nodes) seem to have such an addition.

I'm probably mistaken somewhere, but I don't know where. Let me know if you need me to clarify something; I don't know if what I said made sense.

I don't know about fib() but I work with real instances of recursion e.g. scanning file servers. But in recursion you're always building a stack and eventually you'll blow the stack if you queue too much up. You may or may not have values that are retained until the procedure destructs. It all depends on the implementation. But once the instance destructs the memory should free.

So I pass

\\myserver\

1 set

it then goes and searches

for every folder it calls another instance to search that folder, and for each folder within it calls again, right?

but once it gets to

\\myserver\some\department\some\really\long\obfuscated\nest\mess\etc\

and it starts backing out, then the queue shrinks and in this case will shrink and grow dynamically.

I assume in your case without bulging my eyes out on a scholarly dissertation that you're probably taking values from the recursion and using it for the next thing.

It seems in this case they are doing a study of the pros and cons of implementing different methods of recursion. From what I glean it has to do with the fundamentals of the calculation not the act of recursion itself that differentiates the examples cited in your linked study.

Oh, okay. The program flow actually follows the arrows around the tree. It's not that all the level 1 nodes are visited first, then the level 2 nodes, etc. That's called "breadth-first" traversal, and it isn't suitable for recursive evaluation. For example, to evaluate fib(5), it needs to evaluate fib(4) and fib(3). So fib(5) is at the root of the tree, and fib(4) is the left child and fib(3) is the right child. Then it completely evaluates the left child before even touching the right child. So when it's evaluating the left child fib(4), the program hasn't even started evaluating the right child fib(3), so there's no memory cost associated to right subtree when the program is in the left subtree. Also, when it starts evaluating the right child fib(3), the only things the program needs to remember from the previous computation are the value of fib(4) and that it needs to add that value to the value of fib(3), to be computed presently, to evaluate the parent node.

Wow, nice. That makes a lot more sense now, thanks!

Later in that book they take advantage of this when demonstrating memoization: since the values for each successive fib n were calculated when determining fib n-1, the values needed for fib n are all already stored, reducing the problem to just lookups and additions for each successive value.

That is to say, to get fib 4, you first need to calculate fib 3 + fib 2. You start by calculating fib 3, which is fib 2 + fib 1, so you get fib 2, which is fib 1 + fib 0. Since fib 1 and fib 0 are known values, you just add those to get fib 2. So far the same as the version above. The difference is that now, the result of fib 2 is the stored by the tabulator filter, so that when you go to get fib 2 again while calculating fib 3, instead of recomputing fib 2 along the way, it just gets read out of the table. Now that fib 3 is calculated, it get stored, too, so fib 4 just becomes fib 3 + fib 2 without having to recompute them. This

But that trick is still a long way off in the book, so you probably shouldn't worry about it yet; by the time you get there, it should make more sense. Have fun reading it; it's a real challenge to get through, but if you make it, you should understand programming in general much better. If this is for a class, I hope you have a really good professor, because it's a tough book to teach from - but again, well worth it if done right.

Finally, I should add that Scheme isn't quite so limited a language as they make it seem; they're intentionally using only a minimal subset of an already small language, because one of their goals is to show how little is actually needed for programming. They actually walk you through writing versions of a lot of functions that are normally built into Scheme (or part of the standard library), to demonstrate how they work. A lot of people get impatient with SICP because of that, but it really does explain a lot of things that are usually handwaved elsewhere. Think of it as a sort of programing Tai Chi; slow and harder than it looks at first, but if you stick to it you can get impressive results.