Thinking About Recursion

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)

I skimmed the description of recursion. Seemed a bit long for my taste.

I was taught how to write a recursive function like this:

“Write the function signature, the docstring, and the base case. Then assume the function already works, and use it to implement the rest of the code”

The only recursion that still bothers me is Clownsort / Stooge sort [0]. That such an algorithm would work is still not my gut feeling.

[0] https://en.wikipedia.org/wiki/Stooge_sort

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.

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.

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.