Intro:
In this article, I am giving information about recursion, a powerful technique which can be used in place of iteration. Generally recursive solutions are less efficient than iterative solutions to some problems. However the recursive solutions to some problems are so natural that it is very difficult to solve them iteratively. Therefore we can not skip this recursion importance.
Some Definition and Examples:
The concept of recursion is just like a set of Russian dolls which fits inside one another, that is inside the first doll is a smaller doll, inside which is yet a smaller doll…. In other words you can say that the recursion keeps reproducing its smaller and smaller examples of its until a solution is found.
And when we talk about recursion in a high-level language such as C/C++, its definition is as: the ability of a function to call itself within itself. A situation in which a function calls itself is said to be recursive call. The word recursive means “having the characteristics of coming up again and again, or repeating”. In this case, a function call is being repeated by the function itself. Recursion is very powerful feature of C language and is used in more advanced programs. But until you understand how to use recursion effectively, you must not use recursion.
In C language, any function can call any function, even itself. You will be surprised to know that even main () can be called recursively. And there is no limitation on any number of recursive call.
Let us understand the concept of recursion by taking a recursive example. We all know that C does not provide a power operator. So let us firstly write a simple function to calculate Xn (without recursion) where X and n are both non-zero, positive integer.
power(int a, int b)
{
int i, val;
val = 1;
for(i=1; i<=b; i++)
val = val * a;
return (val);
}
Now i am rewriting this power function using recursion. Before writing this recursive function, let me make you understand the arithmetical approach to solve this problem. We know that
If we know Xn-1 we can easily calculate Xn. This definition is a classic recursive definition, that is the definition is given in terms of a smaller version of itself.
Same way
If we know the value of Xn-2 we can calculate Xn-1 and thus calculate Xn.
Xn = X(X(Xn-2)
And this process will continue until the innermost expression becomes X0. We know what X0 is, it is 1. Whenever we use recursion, we should remember the answer without resorting to a recursive definition. The case for which an answer is explicitly known is called as base case and the case for which the solution is expressed in terms of a smaller version of itself is called the recursive case or general case. In this example, “in terms of smaller version of itself” means that the exponent is decremented each time. Thus we can say that the base case is the case for which the solution can be stated non-recursively.
Now it is easy to write the recursive function for Xn..
power(int x, int n)
{
int val ;
if (n==0 ) /* base case */
return (1) ;
else
{
val = x * power(x, n-1) ; /*recursive case */
return (val) ;
}
}
Now trace the execution of this recursive function with x equal to 2 and n equal to 4. During each call the power() function passes the actual parameters to the version being called. The value of ‘x’ is same for each power function call, but the value of ‘n’ is decremented by 1 for each call until ‘n’ becomes 1. When ‘n’ becomes 0, the power() function starts returning a value, which is 1 in our example. This value of power() function is passed back to the previous version that made this call and this process of returning values will continue until the value of the power can be passed to the original call.
see what happens during each call.
Call-1 – power() is called with ‘x’ equal to 2 and ‘n’ equal to 4. Since ‘n’ is not equal to 0, so power() is called with ‘x’ and ‘n-1’ as parameters. Execution of the call to the function halts until the result is sent back from this recursive call.
Call-2 – power() is called with ‘x’ equal to 2 and ‘n’ equal to 3. Since ‘n’ is not equal to 0, so power() is called with ‘x’ and ‘n-1’ as parameters. Execution of the call to the function halts until the result is sent back from this recursive call.
Call-3 – power() is called with ‘x’ equal to 2 and ‘n’ equal to 2. Since ‘n’ is not equal to 0, so power() is called with ‘x’ and ‘n-1’ as parameters. Execution of the call to the function halts until the result is sent back from this recursive call.
Call-4 – power() is called with ‘x’ equal to 2 and ‘n’ equal to 1. Since ‘n’ is not equal to 0 now, so power() is called with ‘x’ and ‘n-1’ as parameters. Execution of the call to the function halts until the result is sent back from this recursive call.
Call-5 – power() is called with ‘x’ equal to 2 and ‘n’ equal to 0. Since ‘n’ is now equal to 0, the value of ‘x’ is stored in power(2, 0). Fortunately this call to the function has finished execution, and power() is passed back to the place in the statement from which the call was made.
Call-4 – this call to the function power() is now complete. The value ‘1’ is returned and power() passes this value back to the place in the statement from which the call was made.
Call-3 – this call to the function power() is now complete. This value (which is 2) is multiplied by ‘x’ and power() is passed back to the place in the statement from which the call was made.
Call-2 – this call to the function power() is now complete. This value (which is 4) is multiplied by ‘x’ and power() is passed back to the place in the statement from which the call was made.
Call-1 – this call to the function power() is now complete. This value (which is 8) is multiplied by ‘x’ and power() is passed back to the place in the statement from which the call was made. Since the first call has now been completed, that is the final value of the function power().
Figure-1 the function of power with the block diagrams. Each block calls the power function with the value of actual parameters.
Initially we call power function as:
Figure 1
If you find this example not crystal clear then let us study another recursive function, which calculates the factorial of a number. If we have a positive integer ‘n’, then ‘n’ factorial is defined as the product of all integers between ‘n’ and 1. For example, 4 factorial equals 4*3*2*1 = 24. The factorial of 0 is defined as 1. Generally the exclamation mark (!) is often used to denote the factorial function. Thus the factorial of a number ‘n’ is written as:
n! = n * (n-1) * (n-2) * (n-3) * .... *3 * 2 * 1
Or you can say
n! = n * (n-1)!
Now this expression looks like a recursive definition. (n-1)! Is a smaller instance of n!. Same way
n! = n * ((n-1 ) * (n-2)!)
And this process will continue until n becomes zero and 0! is defined as 1. Thus when ‘n’ is equal to 0, we can set the result to 1.
Here is the function that implements this task.
factorial(int n)
{
if ( n == 0 )
return (1) ;
else
return (n * factorial (n-1)) ;
}
Now let us look at the execution of this program by assuming ‘n’ to be 5.
Call-1 – factorial() is called with ‘n’ equal to 5. Since n is not 0, the else statements will be executed. The very first statement in else block is using a recursive call with (n-1) which is 4, so the assignment will not be completed and hence no value is returned.
Call-2 – factorial() is called with ‘n’ equal to 4. Since n is not 0, the else statements will be executed. The very first statement in else block is using a recursive call with (n-1) which is 3, so the assignment will not be completed and hence no value is returned.
Call-3 – factorial() is called with ‘n’ equal to 3. Since n is not 0, the else statements will be executed. The very first statement in else block is using a recursive call with (n-1) which is 2, so the assignment will not be completed and hence no value is returned.
Call-4 – factorial() is called with ‘n’ equal to 2. Since n is not 0, the else statements will be executed. The very first statement in else block is using a recursive call with (n-1) which is 1, so the assignment will not be completed and hence no value is returned.
Call-5 – factorial() is called with ‘n’ equal to 1. Since n is not 0, the else statements will be executed. The very first statement in else block is using a recursive call with (n-1) which is 0, so the assignment will not be completed and hence no value is returned.
Call-6 – factorial() is called with ‘n’ equal to 0. Since n is equal to 0. This call to the function factorial() has finished executing. The result 1 is sent back to the call 5.
Call-5 – the assignment statement in this copy can now be computed. This call has now completed and returns the value 1.
Call-4 – the assignment statement in this copy can now be computed. This call has now completed and returns the value 2.
Call-3 – the assignment statement in this copy can now be computed. This call has now completed and returns the value 6.
Call-2 – the assignment statement in this copy can now be computed. This call has now completed and returns the value 24.
Call-1 – the assignment statement in this copy can now be computed. This call has now completed and returns the value 120. Since the first call has now been completed, that is the final value of the function factorial().
Figure-2 summarizes this execution process as :
Figure 2
Now briefly write down the ideas before writing a recursive algorithms:
- understand the problem clearly
- determines the base case(s)
- determines the recursive case(s)
No doubt the iteration solutions to above these two recursive problems are simpler and much more efficient. So please do not puzzle. Take a more complicated problem – one in which the recursive solution is not immediately apparent.
Now write a function, which converts a decimal integer (base 10) into a binary integer (base 2).
Before writing the function directly, let us understand how does this conversion take place? A decimal number (base 10) is converted into a binary number (base 2) as follows:
- take the decimal number ‘n’ and divide it by two
- write the remainder the rightmost digit in the output
- replace the original number with the quotient
- repeat, placing each new remainder to the left of the previous remainder
- Step (iii) and (iv) will continue until the quotient is zero.
we want to convert a decimal 34 into binary,
34 / 2 = 17
34 % 2 = 0 print remainder as: 0
17 / 2 = 8
17 % 2 = 1 place the remainder to left of the previous one as: 10
8 / 2 = 4
8 %2 = 0 place the remainder to left of the previous one as: 010
4 / 2 = 2
4 % 2 = 0 place the remainder to left of the previous one as: 0010
2 / 2 = 1
2 % 2 = 0 place the remainder to left of the previous one as: 00010
1 / 2 = 0
1 % 2 = 1 place the remainder to left of the previous one as: 100010
This is clearly a by hand algorithm for a calculator and paper. Expression such as “to the left of” are certainly not implemented in C as yet. One may think that the problem could be implemented with a straight forward iterative algorithm as follows:
binary(int n)
{
if (n == 0 )
{
printf(“%d”,n);
return;
}
else
while ( n != 0 )
{
printf("%d",(n%2));
n = n /2;
}
return ;
}
When we use this function with the decimal integer number 34 we will get the output: 010001
This answer is just the reverse of the expected output. In this first remainder is printed firstly, then second, third and so on. But in reality we need to print the last remainder first, then second last remainder, third last remainder and in last we should print the first remainder. This is just like a recursive definition in which the last call returns the value first. We can summarized by saying that for any given number, n, it should print n%2 after (n/2)%2 has been printed.
Here is the recursive algorithm that converts a decimal integer number into a binary number.
binary(int n)
{
if (n == 0 )
return ;
else
{
binary(n/2);
printf("%d",(n%2));
}
}
Now when we use this function with the decimal integer 34 we obtain the output: 100010.