> 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.
For 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.
You can write bottom up algorithms using recursion too. It still technically goes down first, but does the real work on the way up.