>> This is because a recursive sub-function never solves the exact same problem as the original function, but always a simpler version of an original problem.
> This isn't always true. There are plenty of recursive functions whose purpose is merely to climb until a condition is met that there are no more rungs in the ladder.
What do you mean here? What is the ladder in your analogy? The stack? Is the "a condition" that the stack has reached its limit or that you have reached a base case?
If computing f(50) requires computing f(50), it will never end. Likewise if you have a base case at 0, if f(50) requires computing f(51), it will never end. You must solve a problem closer to your base case than the original problem.
> Recursion is difficult because it isn't just taught, it is mythologized as the potentially infinite source of a one's love for programming. If teachers similarly mythologized the "switch" statement I'm sure they could confuse the topic of conditionals just as easily.
I don't think that recursion is mythologized. It allows you to express the core idea of the algorithm really succinctly.
For example defining the Fibonacci sequence just requires the beginning numbers and the rule for progression.
fib(n):
if n = 0 or 1: return 1
return fib(n-1)+fib(n-2)
It is much simpler than the iterative solution (though generally being inefficient).
Often the simplicity gained by using recursion (if you are comfortable with it) makes it possible to understand algorithms you could not understand the iterative form of.
Also, recursion is simply more powerful than just while or for loops (you need stacks as well). And when you add stacks into the mix, iterative programming can get very confusing.
Simpler than the iterative is hard to argue -- it's closer to a strict mathematical definition but the iterative version can also be setup very simply too.
To say one is more powerful is really false. I think recursion is great, and for some situations it should be the go to method, but anything you can write iteratively you can write recursively and vice-versa.
> To say one is more powerful is really false. I think recursion is great, and for some situations it should be the go to method, but anything you can write iteratively you can write recursively and vice-versa.
I mean powerful in a strict theoretical sense. Without using a way to freely allocate arbitrary memory, recursion can compute things loops cannot. The ackerman-peter function is an example.
Loops however can be trivially converted into functions.
Therefore because loops can be converted into recursive calls and recursive calls cannot always be converted into loops. Recursion is more powerful.
What do you mean here? What is the ladder in your analogy? The stack? Is the "a condition" that the stack has reached its limit or that you have reached a base case?
If computing f(50) requires computing f(50), it will never end. Likewise if you have a base case at 0, if f(50) requires computing f(51), it will never end. You must solve a problem closer to your base case than the original problem.
> Recursion is difficult because it isn't just taught, it is mythologized as the potentially infinite source of a one's love for programming. If teachers similarly mythologized the "switch" statement I'm sure they could confuse the topic of conditionals just as easily.
I don't think that recursion is mythologized. It allows you to express the core idea of the algorithm really succinctly.
For example defining the Fibonacci sequence just requires the beginning numbers and the rule for progression.
It is much simpler than the iterative solution (though generally being inefficient).Often the simplicity gained by using recursion (if you are comfortable with it) makes it possible to understand algorithms you could not understand the iterative form of.
Also, recursion is simply more powerful than just while or for loops (you need stacks as well). And when you add stacks into the mix, iterative programming can get very confusing.