Functions in C - Part 3 of 5

Recursion, as the name suggests, requires a function to be capable of calling itself. C supports implementation of recursive functions by allowing a function to call itself repeatedly. Let us look at a couple of examples.

Example 1

A recursive function used to compute factorial of a number.

 /* Compute factorial of n */
 long int fact(int n) 
 {
	if(n <=1) 
		return(1); 
	else 
		return(n * fact (n -1)); 
 }

Example 2

A recursive function used to generate numbers which are in Fibonacci sequence e.g. 1, 1, 2, 3, 5, 8, 13,...

The sequence of Fibonacci numbers f_n, satisfy the recurrence relationfn = fn-1 + fn-2, for n > 2 and f₁ = f₂ = 1.

 #include <stdio.h> 
 main()
 {
	int n; 
	printf("Give n: ");
	scanf("%d", &n); 
	printf("\nfib(%d) = %d\n", n, fib(n));
 }

 /* Function to find first m numbers which are in Fibonacci sequence */
 int fib(int m) 
 { 
	if(m == 0) return(1);
	else if(m == 1) return(1); 
	else return(fib(m - 1) + fib(m - 2));
 }

The only difference between a recursive function call and an ordinary function call is that a recursive call creates a second activation of the subprogram during the lifetime of its first activation. If the second activation leads to another recursive call, then three activations may exist simultaneously, and so on. The only new element introduced by recursion is the multiple activations of the same function that can exist simultaneously at some point during its execution. Thus, due to existence of several activation records, recursive functions can be quite memory intensive.

Although the recursive call feature enhances the power of the language and is appealing from the programmer's point of view, many problems, however, can be solved with the help of repetitive statements, without taking recourse to recursive function call. For example, the following code illustrates the implementation of factorial computation without recursive call.

Implementation of a non recursive method to find factorial of a number:

 #include <stdio.h> 
 main()
 {
	int n, i, factorial; 
	printf("Enter a number: ");
	scanf("%d", &n); fflush(stdin); 
	printf("The number input is: %5d\n", n);
	
	if(n == 0)
		printf("\nThe factorial of 0 is 1\n");
	else
	{
		factorial = 1;
		for(i=1; i <= n; i++)
			factorial = factorial * i;
		printf("The factorial of %5d is %5d\n", n, factorial);
	}
 }

It may be mentioned that from computational efficiency point of view it would be desirable to replace recursive function call by such repetitive statements, whenever possible. This is due to the reason that implementation of the recursive function call will lead to creation of activation records and jumping to the function code and returning from it at the end of computation, as discussed above. Such activities will involve additional computational overhead, which will not occur when the problem is solved using a repetitive block of statements. However there are many recursive cases which cannot be implemented by mere repetitive statements.

To effectively substitute the recurrence relation, complex data structures like a user stack are used. To illustrate this, consider the following problem called Tower of Hanoi which requires a set of disks of increasing diameter to be moved from first peg to second taking the help of a third peg, so that at every stage a disk of smaller diameter can be placed over another having larger diameter. At no stage of the disk movement this ordering should be violated.

A program to solve the Tower of Hanoi problem:

 #include <stdio.h> 
 main()
 {
	int n;
	printf("Give n: "); 
	scanf("%d", &n);
	towers(n, 'A', 'B', �C�); 
 }

 void towers(int m, char from, char to, char via)
 {
	if(m == 1) 
	{ 
		printf("Move disk from peg %c to peg %c \n", from, to); 
		return;
	}
	else
	{
		towers(m-1, from, via, to);
		printf("Move disk %d from peg %c to peg %c\n", m, from, to); 
		towers(m-1, via, to, from);
		return;
	}
 }

Run the above code and observe the results for different values of n. Also, try to simulate the above program with pen and paper, by drawing the static code segment and activation records for a smaller case where n=3 and figure out how the instructions will execute in the computer's memory, how multiple activation records will be created for the function towers, the sequence of execution and the sequence in which activation records will be destroyed.

Exercise

Is it possible to implement this problem without using recursive function call? If so, try it.

The following recursive function called Ackerman function (for arbitrary values of m and n), is difficult to implement without the help of recursive function call.

Ackerman's function A(m, n) is defined as:

 A(m, n)  = n + 1             - if m = 0
            A(m-1, 1)         - if n = 0 
            A(m�1, A(m, n-1)) - otherwise

 /* An implementation of Ackerman's function in C */ 
 int a(int m, int n)
 {
	if(m == 0) 
		return n + 1; 
	else
	{
		if(n == 0) 
			return a(m-1, 1);
		else
			return a(m-1, a(m, n-1)); 
	}
 }

Exercise

Can you express each of the following algebric formulae in a recursive form? If, yes, write C program to implement the same.

 (a) y = x1 + x2 + ... + xn
 (b) y = 1 + 2x + 4x2 + 8x3 + ... + 2nxn
 (c) Y = (1 + x)n

Lab work

1. Write a C program to compute xⁿ where x is a floating point variable and n is an integer.
2. Write a C program to find the greatest common divisor of two integer numbers.
3. Write a C program to find the Length of a string of characters.
4. Write a C program to compress a string of character by eliminating blank spaces.
5. Write a C program to compute e^x, where x is an integer number using the formula:
   ex = 1 + x + x2/2! + x3/3! + ...
   Compute to a given degree of accuracy ?, where ? = 0.0001
6. The combination comb(n, m) where n and m are integer variables and n ? m, can be computed using the following recurrence relation:
   For n, m ? 1,
    Comb(n, m) = comb(n-1, m) + comb(n-1, m-1)
    Comb(n, m) = 1, if(n == 1) or (m == 0) or (n == m)
   Write a recursive C function to compute comb using recursive relation. Can you compute comb without using recursive function call?