Recursive Loops

Last week I wrote about loops and how some students seem to have trouble with them. On the link to it from Facebook one friend of mine asked “what’s a for loop?” He’s a Scheme sort of guy and a lot of looping in functional languages like Scheme is done with recursion. So I thought I should play with recursive loops a bit. Just for the fun of it. Yeah, some of us do play with code for fun. Recursion in general gives some students trouble. I must confess that I struggled with it for a while. For me I found the idea of using recursion for looping to be unnecessarily complicated. That is probably a function of not using a functional language though. This is probably a good part of the argument for students learning several programming paradigms BTW.

Students of mine have several times discovered recursion on their own. Often this is because they are learning a new programming language so they know that loops exist but they do not know the syntax in the new language. So they think “well I can have the function call itself.” Often they decide to have main (or equivalent) call itself. Generally not a great idea. The worst part is that they don’t think about all the parts of a loop – specifically they forget about the check to see if the loop is finished. This is when we have a teachable moment to talk about stack overflows.” So generally it is best to have a separate routine that calls itself after being called initially from outside. For example:

 Module Module1
  
     Sub Main()
         GoDeep(0)       ' Set initial condition in first call
     End Sub
  
     Sub GoDeep(ByVal i As Integer)
         Console.WriteLine("Up   " & i.ToString)
  
         If i < 9 Then       ' Are we done yet?
             GoDeep(i + 1)   ' if not, change the condition and call ourselves again
         End If
  
         Console.WriteLine("Down " & i.ToString)
     End Sub
 End Module

This program prints out the following:

image

It’s still a loop of sorts and it follows all the same rules for for loops, while loops, do loops and all the other sorts of loops in procedural languages.

Of course if you use recursion too deeply you get something like this:

image

This demonstrates one other problem with recursion though – it takes a lot of resources. So while there are times when nothing but recursion will do I generally prefer “regular” loops when those will do the trick.