Delphi Tutorial - A Beginners Guide to Recursion

'

Introduction

Recursion may at first seem like a complex concept, however, it is actually quite simple and as powerful applications. In this section we are going to look at how to make two recursive functions, a Factorial function and an Exponential function. But first, what is recursion? Recursion is when a function or procedure repeatedly calls itself until a certain condition is met.

Factorials

The Factorial function keeps calling itself until the number passed to it reaches zero. This happens because F! (0) = 1 is a numerical constant. When this value of zero is reached, the function stops calling itself and the value of one is sent back to the calling function. This function then calculates a value and sends it back to the previous caller, and so on, and so on. The equation to find F! (N) Is F! (N) = N * F! (N - 1). To make this recursive procedure, we have to break the equation down into the three parts that exist. First, F! (N) only takes one integer parameter and returns one integer parameter. That means that our function declaration is going to look something like this:
  Function Factorial(num: integer): integer;
Next, There is a special case. This is when F! (0) is reached. To accommodate this, we have to add a conditional statement which will look something like this:
   If num = 0 then
     result := 1
   else
     ...
Finally, we need to account for what F! (N) is equal to, which is N * F! (N - 1). This will look something like this:
   result := num * Factorial(num - 1);
When we put this all together, we have a function that will look like this:
   Function Factorial(num: integer): integer;
   Begin
     if num = 0 then
       result := 1
     else
       result := num * Factorial(num - 1);
   End;
Now lets try this function with a value. We will trace the execution of Factorial(6).
      Factorial(6) = 6 * Factorial(5)
         Factorial(5) = 5 * Factorial(4)
            Factorial(4) = 4 * Factorial(3)
               Factorial(3) = 3 * Factorial(2)
                  Factorial(2) = 2 * Factorial(1)
                     Factorial(1) = 1 * Factorial(0)
                        Factorial(0) = 1
                     Factorial(1) = 1 * 1
                  Factorial(2) = 2 * 1
               Factorial(3) = 3 * 2
            Factorial(4) = 4 * 6
         Factorial(5) = 5 * 24
      Factorial(6) = 6 * 120
                   = 720
Voila! Now you have a simple recursive function to calculate the factorial of an integer number. One thing that you will have to check for before putting numbers into this function: Is the number greater than or equal to zero? This could be a simple check before the function is called. Once you get your mind thinking in three dimensions, even the most difficult recursive functions become easy.

Exponents

Let us now try to make a recursive function to calculate BN. Answer the following questions: How many values do we have to pass to the function? How many do we need back? Is there any special case? What is the recursive equation to calculate BN? First, how many values do we have to pass to the function? The answer is two: The base and the exponent. How many values do we need to get back? We only need to get back the result of BN. What is our function declaration going to look like? Something like the following:
  Function Pow(Base, Exponent: integer): integer;
Second, Is there any special case? Yes there is. Another numerical constant that we are going to base this function on is N0 = 1. So if the exponent is equal to zero, then the result is going to be one. This will look a lot like the special case in the factorial.
  if Exponent = 0 then
    result := 1
  else
Finally, what is the recursive equation to calculate BN? The recursive equation to calculate BN is BN = B * BN - 1. Again this will look like the line of calculation in the Factorial function.
  result := Base * Pow(Base, Exponent - 1);
When we put it all together we get this:
  Function Pow(Base, Exponent: integer): integer;
  Begin
    if Exponent = 0 then
      result := 1
    else
      result := Base * Pow(Base, Exponent - 1);
  End;
Now lets trace the execution of Pow(3, 4).
      Pow(3, 4) = 3 * Pow(3, 3)
         Pow(3, 3) = 3 * Pow(3, 2)
            Pow(3, 2) = 3 * Pow(3, 1)
               Pow(3, 1) = 3 * Pow(3, 0)
                  Pow(3, 0) = 1
               Pow(3, 1) = 3 * 1
            Pow(3, 2) = 3 * 3
         Pow(3, 3) = 3 * 9
      Pow(3, 4) = 3 * 27
                = 81

A Final Word

As you can see it only takes a few lines of code to make a powerful function and although this looks like a difficult concept to master it is not. These two examples of recursion are some of the simplest examples out there. In a following lesson on Sorting, you will see a more complicated example of a recursive procedure in the Quick Sort algorithm. The sorting and searching tutorials are considered to be intermediate computer programming concepts. Linked Lists, and Double-Linked Lists is an advanced topic that will be covered later.

Editors Notes

This article was originally written by Bryan Coutch aka Oracle whose web site which contains other articles used to be at www.geocities.com/SiliconValley/Haven/7959. This site no longer exists, if any body knows of its new location then please let me know .Thanks again Bryan for this article. Another example of using recursion (in this case for scanning directories) can be found in the article on callbacks.
Google
Web www.Delphi-Central.com
Delphi Central - Delphi Programming Tutorials, Hints and Tips