Thinking About Recursion
solipsys.co.uk
Thinking About Recursion
1–10 of 42 posts
Re: Thinking About Recursion
#2I like thinking about variables as boxes with labels. Hadn’t heard that before, but seems like a simple way to teach people.
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”
Re: Thinking About Recursion
#3To think about recursion, you first have to think about recursion.
Re: Thinking About Recursion
#4I like thinking about variables as boxes with labels. Hadn’t heard that before, but seems like a simple way to teach people. 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”
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.
Re: Thinking About Recursion
#5I like thinking about variables as boxes with labels. Hadn’t heard that before, but seems like a simple way to teach people. 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”
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.
I’m not talking pointers here, simply references.
Re: Thinking About Recursion
#6IMO my favorite way to think about recursion is to build up a call stack and then draw the return arrows.
Re: Thinking About Recursion
#7I 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.
Re: Thinking About Recursion
#8I 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…
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.
Re: Thinking About Recursion
#9I 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…
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.
Re: Thinking About Recursion
#10One 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)