Recursive Loops

Computer Science Teacher
Computer Science Teacher - Thoughts and Information from Alfred Thompson

Recursive Loops

  • Comments 1

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.



  • Well, you should give a link to tail recursions at the end. Using these you do not have problems with StackOverflows.

    Regards,

    Malte

Page 1 of 1 (1 items)