One of my favorite ways of thinking about recursion (and proofs by induction) is the recursion goblins.
When you're writing a recursive function, you don't worry about how you got your input. The recursion goblins took care of that.
You also don't need to worry about what will happen to the thing that you return. The recursion goblins will take care of that, too.
All you need to worry about is what's happening in between the curly brackets, which is that you should make your problem a little smaller. The recursion goblins will take care of the rest.
This was weirdly freeing for me in CS 101/102/103 etc.; I was getting way too wrapped up in trying to visualize the recursion from start to finish, and that's a crapshoot at the best of times, even if it's sometimes important. Much more often, though, you can get a lot done a lot faster if you trust the goblins!
(Thanks to Professors Shindler and Cote for this one)
Working a problem from bottom-up flushes out a lot of the incidental information, making the problem much easier to comprehend. By using the goblin analogy you're focused on the last call, and working back from there.
The Refactoring people knew this, and the Mikado method is essentially a way to find the 'bottom' when all you can see is the top of the rabbit hole, so you can use these other skills.
The challenge is to decide on the specification of what your function inputs and what it outputs. Get specification right, implement it as you describe (ignoring the task of your recursion goblins), and it'll work. Get the specification wrong, and the implementation will either be difficult or impossible.
It is helpful, of course, if someone else has defined a workable specification for you already.
One of my favorite ways to think about recursion is that it's a shitty technique that can and will blow up your stack.
When I try to solve a problem with recursion, then I have two problems.
It's also a great way to filter out morons in interviews. If they ask for a recursive solution, and I tell them that it's a shitty solution, and if they don't immediately agree, then I know I'll be working with morons.
Recursion is a powerful, relatively low-level approach, and the price for expressive power is readability, but it has legit use cases. What you said has a grain of truth in that usually you should prefer combinators like map or filter (if you're doing FP), but just throwing away recursion is silly. Having a strong opinion on it and not seeming to know about TCO is also not a good look.
I don't think it's necessarily more difficult to read, especially with the mindset of the "recursion goblins" mentioned in another comment here, where one only looks at the current iteration and does not care about, where input argument comes from.
But of course, if what one wants to do can be expressed using map and filter and such, why write some recursive procedure.
It’s how I teach people. I also think of variables as boxes and labels. Tje caveat is that for a non-primitive datatype, I put the address of a vault in the box and will go to the vault, everytime I use the value of the variable.
When you write recursive functions like this, you should keep in mind to get strictly closer to your base case with each recursive step (for some feasible definition of "closer"), otherwise you might never reach that base case.
I do a similar thing but with functions: running functions are boxes with labels, function definitions are blueprints of boxes. I use it in videos [1] to explain recursion.
This was how I was "taught" recursion, with (Lucas) Towers of Hanoi. Ugh! I still remember the mostly-filled in function with 2(?) recursive calls placed, for us to fill in the arguments. How the heck would that ever work? was all I could think. I don't think a single person in the class had any idea of progress until the teacher, kinda exasperated, just told us. And we still didn't get it, of course. I get it now, but only from a more task-oriented mindset, not Java Mad Libs.
The only recursion that still bothers me is Clownsort / Stooge sort [0]. That such an algorithm would work is still not my gut feeling.
I think the intuition behind your Stooge sort example is that for an array separated into three segments:
A | B | C
The first sort moves the largest elements of A and B into B. The second sort moves the largest elements of B and C (and therefore of A, B, and C) into C. And the final sort properly orders the elements within A and B.
Ok but what does your intuition say about the first step?
> If the value at the start is larger than the value at the end, swap them.
What if we skip that? Broken sort? Is that step necessary, and if so, what's the edge case? Why even mention it? I hope I don't seem combative, I just find my intuition doesn't quite cover this problem.
› It's important to realise that variables in mathematics and variables in programming have a lot in common, but they are not the same thing!
I think the stated "differences" are actually similarities with programming languages.
› In mathematics, sometimes a "variable" is a place-holder for a value one may choose arbitrarily from a collection, and which is then used in some process,
That pretty much perfectly describes a function parameter: for a formal correspondence, universal quantification corresponds to dependent function types.
› In fact, sometimes we find that there is no value satisfying the requirements we have placed on the variable, so in a sense it doesn't exist at all!
That's what happens when your variable's type turns out to be uninhabited, like an empty enum.
› It seems to me, speculating idly and with no research to back me up, that recursion has similar conceptual challenges as Mathematical Induction and Proof By Contradiction.
The author used proof by contradiction as part of a proof that the well-ordering principle implies the principle of mathematical induction, but (1) that links recursion and proof by contradiction exactly as much as it links recursion and modus ponens, and (2) mathematical induction is usually taken to be the more fundamental rule anyway, so this bit doesn't make much sense to me.
› In mathematics a function doesn't even need to have a rule to tell you what it is,
It depends on your definition of a function. ;)
Related: the author lists rules such as "A finite path from an instance back to one of the simplest", which are formalized in the concept of a well-founded relation.
I tried to explain recursion to my son with the monks from "Towers of Hanoi": What is a monk handing out to the next one? Is he waiting? What is a monk's contribution to the answer? How many monks do we need? What does the last monk do? Which monk gives the answer, the first one or the last one?
I always thought recursion was very elegant, but until now I was using it to scan through folders on the file-system and that was about it.
Then I had an interesting problem at work where recursion seemed the most elegant solution ... but I quickly encountered errors that were not caught in a try catch block and made the program fail silently.
I'll admit my ignorance, but I thought a stackoverflow was a "feature" of low level programming languages such as C and C++ since I never encountered one in 10 years of coding in C#.
So it seems my love for recursion will have to remain mostly platonic and I'll have to use those unappealing loops for a while.
If you're getting a stack overflow, you might check if your language supports tail call optimization, or just known as tail recursion. Not all environments support this, but if you can rearrange your recursive function it would avoid the overflow.
The short version of the tail call story is only one copy of the stack frame is kept, instead of all of the frames on the way down.
You really need language support to make recursion the best practical solution for most problems. However, even when working in "normal" languages like C#, I find that recursion has utility in designing solutions--it is often easiest to find a provably-correct solution for an inherently recursive problem by actually designing a recursive algorithm; you merely then have to perform some compiler work yourself to transform that initial design into an efficient iterative implementation.
C# from .Net 64bit supports tail-call optimization as far as I know. If you write your function in a tail recursive way it will be optimized and you won’t have any stack overflow if you use a C# version more recent than that.
Recently I was reading about digital signal processing and the difference between finite and infinite response filters.
Although probably not the way to teach it, it seems like there's a close relationship? A FIR filter is matrix multiplication on delayed inputs with a limited amount of delay, while infinite response filters use feedback in a way that seems similar to memoization of a recursive function on all previous inputs.
When you're writing a recursive function, you don't worry about how you got your input. The recursion goblins took care of that.
You also don't need to worry about what will happen to the thing that you return. The recursion goblins will take care of that, too.
All you need to worry about is what's happening in between the curly brackets, which is that you should make your problem a little smaller. The recursion goblins will take care of the rest.
This was weirdly freeing for me in CS 101/102/103 etc.; I was getting way too wrapped up in trying to visualize the recursion from start to finish, and that's a crapshoot at the best of times, even if it's sometimes important. Much more often, though, you can get a lot done a lot faster if you trust the goblins!
(Thanks to Professors Shindler and Cote for this one)