1. Computing

Understanding Recursive Functions

By

Recursion is a very simple, yet useful and powerful programmer's tool. As we know, subroutines (functions and procedures) can, and frequently do, call other subroutines. A subroutine that activates / calls itself is called recursive.

Recursion is a general method of solving problems by reducing them to simpler problems of a similar type. A recursive subroutine constantly calls itself, each time in a simpler situation, until it gets to the trivial case, at which point it stops.

Many programmers often avoid this type of subroutine because it can be confusing and complicated. This article is going to make recursion in Delphi simple ... I hope :)

Recursions in Delphi

In Delphi, there are actually two types of recursions possible. In the first, the subroutine only calls itself. This is called direct recursion. Using direct recursion in Delphi is simple, just call the subroutine the way you would call any other. The second type is called mutual recursion. Mutual recursion occurs when routine A calls routine B, and then while routine B is running, routine B calls routine A.

Direct recursions
The general algoithm for a recursive solution to a problem looks like:

 1. Solve recursively (problem)
 2. If the problem is trivial, do the obvious
 3. Simplify the problem
 4. Solve recursively (simplified problem) 
What follows are some of the recursive function examples:

Calculating Factorial

"If the integer number is less than zero, reject it. If the number is zero or one, its factorial is one. If the number is larger than one, multiply it by the factorial of the next smaller number."

In other words: Fact(n) : = n Fact(n-1) if n > 1 otherwise Fact(n) := 1.

 function Fact(inbr:integer):integer;
 begin
   if inbr < 1 then Result := 1
   else Result := inbr * Fact(inbr-1) ;
 end; 

Greatest common divisor

In mathematics, GCD or greatest common divisor is defined as the largest number that divides both of two given integer numbers. Around 2,000 years ago, Euclid gave the following method of computing the GCD of two integers, a and b:

If b divides a, then the GCD is a. Otherwise GCD(a,b):=GCD(b, a mod b)
Where the mod function gives the reminder after integer division.

 function GCD(a,b : integer):integer;
 begin
   if (b mod a) = 0 then Result := a
   else Result := GCD(b, a mod b) ;
 end; 

Exponents m^n

The problem is: how to calculate mN if N is some positive integer number.
 function iPow(base, exp: integer): integer;
 begin
   if exp = 0 then Result := 1
   else Result := base * iPow(base, exp - 1) ;
 end; 

Recursive file search

When looking for files, it is often useful (necessary) to search through subfolders. In the Searching for Files article you can see how to use Delphi's strength to create a simple, but powerful, find-all-matching-files project.

Mutual recursions
You know that in Delphi we can't use an identifier until we have declared it. In other words, Delphi doesn't let one routine call another routine that is defined after it. To make such mutual recursion possible, we need to declare a routine as a forward declaration. To make a forward declaration, add the forward reserved word at the end of the header of the subroutine. Then place the header with the extra forward declaration before the code for the subroutine that will call it. Here's an example of using a forward declaration:

 procedure MyProc1(dummy : integer) ; forward;
 
 procedure MyProc2;
 begin
    MyProc1(5) ;
 end;
 
 procedure MyProc1(dummy : integer) ;
 var
   j:integer;
 begin
   for j:= 1 to dummy do
    ShowMessage(IntToStr(j)) ;
 end;
 
Although recursion looks confusing the first time through, spend some time reviewing those code examples and in no time you won't know how you worked without it.

It is extremely important to design recursive functions with great care. If you even suspect that there is any chance of an infinite recursion, you can have the function count the number of times it calls itself, and thus make sure that if the function calls itself too many times, however many you decide that should be, it automatically quits.

©2014 About.com. All rights reserved.