2 ms·
> I normally think of any recursion as some kind of descent into deeper levels. Maybe I'm being biased due to awareness of stackframes being a common way to imp
by megous 10y ago
> I normally think of any recursion as some kind of descent into deeper levels. Maybe I'm being biased due to awareness of stackframes being a common way to implement recursion.
You can write bottom up algorithms using recursion too. It still technically goes down first, but does the real work on the way up.
- bjterry 10y agoFor a simple example, this is like the difference between function sum(lst) { if (length(lst) > 0) { return head(lst) + sum(tail(lst)); } return 0; } vs. function sum(lst, currentSum) { if (length(lst) > 0) { return sum(tail(lst), currentSum + head(lst)); } return currentSum; } In the first case you don't actually start doing addition until after you get to the end of the list, while the latter is doing addition on the way down.