We have seen that a function can be called from another function. In fact, the C language allows a function to be called from within itself. Such a function is called a recursive function.
Several problems are naturally expressed in recursive form. For example, the recursive definition to determine the factorial of an integer number is given as
n! =n * (n-1)!
Thus, a larger problem of determination of n! is expressed in terms of a smaller problem of determination of (n-1)!. By the above definition, we can calculate (n-1)! As (n-1) * (n-2)!. This definition can be used repetitively to calculate the value of n! as shown below.
n!=n*(n-1)!
= n * (n - 1) * (n - 2)!
= n * (n - 1) * (n - 2) * (n - 3)!
Obviously, this repetitive substitution should stop somewhere. Thus, a recursive definition must have a stopping criterion. As 0!= 1, the complete recursive definition for n! is thus given as
n!=n*(n-1)! if n>0
= 1 if n = 0
Once a recursive definition for the solution of a problem is available, writing recursive functions is very straightforward. A recursive function fact to determine the factorial of a given non-negative integer number n is given below.
/* recursive function to determine factorial of integer number n */
long int fact(int n)
{
if (n > 0)
return n * fact(n - l);
else return l;
}
Note that the function returns a long int value since the factorial numbers grow very rapidly. Now to understand how this function works, assume that it is called from the main function, as shown below.
int main()
{
long int f;
f = fact(2);
printf ("2! = %ld\n", f);
}
The execution of this program is illustrated in Fig in which the arrows indicate the transfer of control from one function to another and the statements executed are shown in bold face. When function fact is called (from the main function), parameter n is assigned the argument value (i. e., 2) and control is transferred to its beginning. As the value of n is greater than 0, the fact function is called a second time from the if statement.
main() calls fact (2)
Control is again transferred to the beginning of function fact, with argument value n -1, i. e., 1. Thus, the function parameter n assumes value 1 in this function call. Since this value is greater than 0, the fact function is called again (third time) with argument value 0.
Control is again passed to the beginning of fact function and the parameter n is assigned the value 0. Now since the parameter value equals 0, the condition in the if statement evaluates as false and the function returns value 1. This value is returned to the second call of the fact function (for which n had value 1).
Now the expression n *fact (n-1) is evaluated as 1 * 1, i.e., 1 and the value is returned by this function call to the calling function, i. e., the first call of the fact function in which the parameter n had a value of 2.
Now the expression n *fact (n-1) is evaluated again in the first call of the fact function as 2 * 1, i.e., 2 which is returned to the main function where it is printed using the printf function.
Note that the fact function given above can be written concisely using the conditional expression operator as shown below.
long int fact(int n)
{
return (n > 0) ? (n * fact (n - 1)) : l;
}
Finally, consider the function definition given below in which the function name has been reused as a local variable name.
long int fact (int n)
{
long int fact;
if (n > 0)
fact= n * fact(n-1);
else fact = l;
return fact;
}
As the function name has been redefined as a local variable, the compiler gives an error when the function is recursively called. The solution to this problem is to use different names for function and local variables.
A recursive approach to determine the sum of digits of a non-negative integer number n can be given as the addition of the rightmost digit of n and the sum of digits of the number obtained by removing this digit from n, i.e., n/10 (integer division). Note that this definition is applicable as long as n has more than one digits, i. e., it is greater than 9. The terminating condition is n < 9, i. e., when n has only one digit in it. In this case, the sum of digits is n itself. A recursive definition to calculate the sum of digits of a non-negative number is given below.
digitsum(n) = n %10 + digitsum(n / 10) if n > 9
=n otherwise
A recursive definition for the digitsum function is given below.
/* determine sum of digits using recursive function */
int digitsum(int n)
{
if (n > 9)
return n % 10 + digitsum(n I 10);
else return n;
}
Illustrates a recursive function for finding squares and square roots.
#include <stdio.h>
#include<math.h>
#include<stdlib.h>
void Frecursive(int A)
{
int square; //Definitionof function
double sq;
square= A*A;
sq = sqrt (A);
if(A>5) exit(0);
printf("%d \t %d \t %lf\n", A, square, sq);
Frecursive (A+1);
}
void main ()
{
int z =1;
clrscr();
printf("number\tSquare\tSquare root\n");
Frecursive (z);
}
Dinesh Thakur holds an B.SC (Computer Science), MCSE, MCDBA, CCNA, CCNP, A+, SCJP certifications. Dinesh authors the hugely popular Computer Notes blog. Where he writes how-to guides around Computer fundamental , computer software, Computer programming, and web apps. For any type of query or something that you think is missing, please feel free to Contact us.
Related Articles
Basic Courses
Advance Courses