Principle of Recursion

Introduction

Functions are the most basic and useful feature of any programming language. A set of instructions that performs logical operations, which could be very complex and numerous in number, can be grouped together as functions (also called procedures). Functions may call themselves or other functions, and the called functions in turn may call the calling function. This process is called recursion and such functions are called recursive functions.

When a function calls itself, either directly or indirectly, it is said to be making a recursive call. A program becomes compact and readable with recursive functions. Recursion is extremely powerful as it enables the programmer to express complex processes easily. Recursive programs are used in a variety of applications ranging from calculating the factorial of a number to playing complex games against human intelligence. 

Let us consider an example of computing the factorial of a number. Factorial is a mathematical term. The factorial of a number, say n, is equal to the product of all the integers from 1 to n. The factorial of n is denoted as:

n! = 1 x  2 x 3 x …….. x n or n! = n x n - 1 x . . . . .  x1 

For example, 10! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10. The simplest program to calculate the factorial of a number is by using a loop with a product variable.

Algorithm below states the iterative process of computing the factorial of n as 10! = 10 x 9 x 8 x ...x1. 

An iterative version of an algorithm to compute the factorial of a number

An iterative version of an algorithm to compute the factorial of a number
1. start
2. Let n be the number whose factorial is to be computed and let Factorial = 1
3. while(n > 1) do
     Begin
         Factorial = Factorial * n 
         n=n– 1			
     end 
4. stop

Above algorithm is iterative algorithms for computing the factorial of n. It is possible to give a recursive definition for factorial too. The mathematical function defined in Eq. above for factorial of n can also be defined recursively as

n! = n x (n - 1)!, where 1! = 1 

This recursive definition of factorial has two steps, as follows:

1. If n = 1, then factorial of n = 1

2. Otherwise, factorial of n = n x factorial of (n - 1) 

int Factorial(int n)
{
    
      if(n <= 1) // end condition
               return 1;
      else
             return Factorial(n - 1) * n;
} 

The Factorial() function is an example of a recursive function. In the second return statement, the function calls itself. The important thing to remember when creat- ing a recursive function is to give an end condition. In above code, the recursion stops when n becomes 1. In each call of the function, the value of n keeps decreasing. However, when the value reaches 1, the function ends. 

Principle of recursion

All recursive algorithms must obey three important laws:

1. A recursive algorithm must call itself, recursively.
2. A recursive algorithm must have a base case.
3. A recursive algorithm must change its state and move toward the base case.

Writing recursive code

The general approach to writing a recursive function is listed in the following sequence:

1. Write the function header so you are sure what the function will do and how it will be called. Identify some unit of measure for the size of the problem the function or procedure will work on. Then, pretend that the task is to write a function that will work on problems of all sizes.
2. Decompose the problem into sub-problems. Identify clearly the non-recursive case of the problem. Make it as small as possible. The function will nearly always begin by testing for this non-recursive case, also known as the base case or the end condition.
3. Write recursive calls to solve those sub-problems whose form is similar to that of the original problem.
4. Write the code to combine, enhance, or modify the results of the recursive call(s), if necessary, to construct the desired return value or create the desired side effects.
5. Write the end condition(s) to handle any situations that are not handled properly by the recursive portion of the program.

Execution of recursive calls

Let us now see how recursive calls are executed. At every recursive call, all reference parameters and local variables are pushed onto the stack along with the function value and return address. The data is conceptually placed in a stack frame, which is pushed onto the system stack. A stack frame contains four different elements:

• The reference parameters to be processed by the called function 
• Local variables in the calling function
• The return address
• The expression that is to receive the return value, if any

Consider the following two lines from the Factorial() function in Program: 

if(n <= 1) 
    return 1;
else 
     return n * Factorial(n - 1); 

Consider the first call as Factorial(4). Now, 

The recursive call works as follows:

Initial Call: factorial(4)

Push: factorial(4) onto the stack.

factorial(4) calls factorial(3).

Push: 4*factorial(3) onto the stack.

factorial(3) calls factorial(2).

Push: 3*factorial(2) onto the stack.

factorial(2) calls factorial(1).

Push: 2*factorial(1) onto the stack.

Base case reached: factorial(1) returns 1.

Now, the stack starts to unwind:

Base case reached: factorial(1) returns 1.

Pop: factorial(1) from the stack.

factorial(2) receives 1 and calculates 2 * 1 = 2.

Pop: factorial(2) from the stack.

factorial(3) receives 2 and calculates 3 * 2 = 6.

Pop: factorial(3) from the stack.

factorial(4) receives 6 and calculates 4 * 6 = 24.

Pop: factorial(4) from the stack.

Final result: 24.

factorial(4) receives 6 and calculates 4 * 6 = 24.

Final result: 24