Back

Iterative versus recursive approaches

Introduction
A recursive routine is a routine that calls itself. An iterative routine is one that loops the same code a number of times, anything from never actually doing the code to many times, depending on the result of a condition or by using a FOR loop. We saw some examples of iteration in 3.2.2d. Any recursive function or procedure can be rewritten as an iterative one. There are some key differences between the approaches.

Iterative versus recursion
An iterative routine to calculate a factorial might be:

Function Factorial_Recurse(number)

      If (number<=1) Output 1
      Output number * Factorial_Recurse (number - 1)

End Function Factorial_Recurse

The same function can be rewritten using iteration:

Function Factorial_Iter(number)

      Total = 1
      If (number <= 1) Output Total
      While (number > 1)
            Total = Total * number
            number = number - 1
      End While
      Output Total

End Function Factorial_Iter

Comparison of iterative versus recursion
Every time a call is made using recursion, the processor in the computer has to stop what it's doing and save all of the contents of special memory boxes in the CPU called 'registers' before it can do the call. After a call has finished, it then has to go to the place it saved the registers (called the 'stack') and put the values back in.

    1. If a recursive routine keeps calling itself, then it has to keep pushing values onto the stack, and ultimately keep taking them off (or 'popping') values off the stack. The problem with this is that the stack is a fixed size, so too many calls and you will quickly fill up the stack and get a 'stack overflow' error. Also, it takes time to push and pop values on and off the stack. As long as there aren't too many recursive calls, then recursion is fast. Too many calls, and relative to iteration, the process becomes slow.
    2. You can see from the two examples above that there are less instructions using recursion. Less instructions means a smaller program, smaller object code and a program that should in theory run faster.
    3. Some people find recursion difficult to follow compared to iterative routines. With practice, however, and knowing how to trace a recursive routine, it does become fairly easy.

Back