Tips for Teaching Recursion

[JFischer00]

I am currently teaching a Computer Science class for middle schoolers. This week we will be covering recursion. I know for many people recursion is difficult to understand and visualize so I was wondering if anyone had any tips or examples that they've used to explain recursion or someone used to explain it to them. Any help is greatly appreciated. Thanks in advance!

[Theguywhobea]

Google "recursion" and then click on recursion when it says "Did you mean recursion?"

[JFischer00]

Just now, Theguywhobea said:

Google "recursion" and then click on recursion when it says "Did you mean recursion?"

That's pretty neat, but I don't feel like it really explains recursion in a programming sense (down the stack until we reach a certain point then back up).

[Mira Yurizaki]

The only time I had to use recursion (since it made sense) was to crawl through a data structure in order to build a visual representation of a tree. I believe the basic idea was if the node wasn't a leaf, then have the function call itself on the branches. Otherwise if is a leaf, return whatever it is you wanted.

 

Otherwise I rarely use it.

[vorticalbox]

39 minutes ago, M.Yurizaki said:

The only time I had to use recursion (since it made sense) was to crawl through a data structure in order to build a visual representation of a tree. I believe the basic idea was if the node wasn't a leaf, then have the function call itself on the branches. Otherwise if is a leaf, return whatever it is you wanted.

 

Otherwise I rarely use it.

I was racing up on function programming for nodejs and this was use to create a tree of a dir you push up the files then pass the folder back recursion.

[MyName13]

Backtracking recursive sudoku solver.

[BlinkTwic3]

Good ole' Fibonacci is usually a good place to start with recursion.  

[Mira Yurizaki]

I just remembered something. I posted something here that uses recursion and has a practical purpose: a Huffman codec.

Huffman codecs require a tree in order to grab the character from the stream of bits. So the tree building mechanism does it recursively.

 

In any case, I often avoid recursion in favor of using a loop if I can. I looked up the page on Wikipedia and an example they gave was for calculating factorials. While that is a use for recursion, you could do the same thing with:

int calc_factorial(n){
  int y = n;
  n--;
  while(n > 1){
    y *= n;
    n--;
  }
  return y;
}

While it's more lines, it's also easier to understand given how a person would calculate a factorial by hand. I prefer easier to understand over "clever tricks."

 

The other issue is that depending on the recursion itself, you could run into an issue where you blow up the call stack. While maybe this isn't much of a problem on systems with a lot of memory, we still have things that have less memory than the original IBM PC running around. The above function only needs to push one thing in the call stack and it can run entirely using two registers. That's cheap. If you were recursively calculate factorials, you would have to push n-1 things on the call stack.

 

So recursions should be used judiciously.

[JFischer00]

I appreciate all the great suggestions and ideas. I understand @M.Yurizaki's point about preferring iteration over recursion for multiple reasons, but I still believe it is a concept that should be covered in some depth in an introductory CS course. As long as tools' strengths and weaknesses are taught, more tools in your toolbox will generally result in better code (and problem solving thought processes since we're talking about CS in general, not just programming).

[Guest]

My friend had a really funny way of explaining it. Went something like 

 

“The definition of recursion is when you follow the definition of recursion is when you follow the definition of recursion.....” 

 

I forget his phrasing but something like that. Someone said you can just explain it with a while or for loop. It does the same thing over and over till a definition is met. 

[PurpleCodes]

[krgesu]

I've used a military chain of command as an example when I was explaining recursion.

[wasab]

On 3/8/2018 at 11:36 AM, M.Yurizaki said:

The only time I had to use recursion (since it made sense) was to crawl through a data structure in order to build a visual representation of a tree. I believe the basic idea was if the node wasn't a leaf, then have the function call itself on the branches. Otherwise if is a leaf, return whatever it is you wanted.

 

Otherwise I rarely use it.

We need it to figure out all the prime numbers. How are you gonna find out prime factors without recursion???

 

It it is all prime numberphiles best friend.

 

Not only that, they are great for complicated sorting algorithms. 

[Mira Yurizaki]

4 minutes ago, wasab said:

We need it to figure out all the prime numbers. How are you gonna find out prime factors without recursion???

 

It it is all prime numberphiles best friend.

 

Not only that, they are great for complicated sorting algorithms. 

I didn't say recursion is totally useless and you should avoid it. I'm only stating what I had to use it for when I did.

 

I also didn't state what I normally work on, but if it helps, almost everything I do has no real practical use for recursion. If you work on algorithms that are better suited for it, then sure, by all means use it.

[wasab]

2 hours ago, gabrielcarvfer said:

Recursion is only difficult if you don't understand why people even bother doing it: not only it looks better, making it easier to read, but also is more similar to the original idea of the algorithm itself.

Show them examples of the same algorithm without and with recursion. The best example you will find, in my opinion, is the merge sort, that uses a divide-and-conquer strategy to sort the input.

 

Doesn't breaking down an input into smaller chunks until you have only one element per chunk, then joining those chunks back in a clever way, resulting in a sorted array sound much more natural than executing an "unknown" i number of passes, sorting chunks of size 2^i  at each pass, until the size of the chunk is equal or greater the input size (that means that the entire input got sorted)?

 

Plus, in case of recursive merge sort, is pretty easy to see that you can break the input on chunks, and put those to be sorted by different threads, using multiple CPUs to do the job, while making the interactive merge sort parallel might not look that easy (but it is, as there are no dependencies between chunks).
 

Why would we need recursion for that? Just brute force, save primes found in a table and then use them to check if a number is prime. 

Can’t do that for factorial tho.

 

Edit: never mind, it is possible. I just done it. I will find some examples in which recursion is needed while looping is not possible.

[impure]

I remember the first time I 'got' recursion. My University had a discussion board for the class and we were all talking about how many lines we did the exercises in and in order to get my solution smaller and smaller I had to use recursion. I think making students try to write solutions with some sort of constraint on the number of lines is a really good way of going about this. Because if you just lecture whenever they hear "Recursion" they'll probably think "Thing I Could Do Using A Loop" and they won't have any incentive to learn.

[Mira Yurizaki]

4 hours ago, wasab said:

Can’t do that for factorial tho.

 

Edit: never mind, it is possible. I just done it. I will find some examples in which recursion is needed while looping is not possible.

Traversing a tree.

 

For every node you need a while loop to traverse the leaves. And for each layer of nodes you have, you need another loop. Since you cannot determine ahead of time how many nodes you have, you can't determine how many layers of looping you need.

 

Which if you were to generalize this, any algorithm that uses a divide and conquer method to find the result.

[Mira Yurizaki]

18 minutes ago, gabrielcarvfer said:

Not being able to determine ahead of time the tree depth doesn't mean you can't traverse a tree. In fact, it's not that hard to write a single loop that can do that, but you will need to store references to go back and forth (if the nodes doesn't have references to their parent node), plus current depth.

That just sounds like a pain in the butt to do though.

[Dune II]

Hi,

 

What I found easy to understand, was getting the total file size from a folder and it's sub folders.

Its easy to check if you're correct and it can be explained step by step visually.