How2Lab Logo
tech guide & how tos..


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 fn, satisfy the recurrence relationfn = fn-1 + fn-2, for n > 2 and f1 = f2 = 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(m1, 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 xn 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 ex, 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?


Share:
Buy Domain & Hosting from a trusted company
Web Services Worldwide
About the Author
Rajeev Kumar
CEO, Computer Solutions
Jamshedpur, India

Rajeev Kumar is the primary author of How2Lab. He is a B.Tech. from IIT Kanpur with several years of experience in IT education and Software development. He has taught a wide spectrum of people including fresh young talents, students of premier engineering colleges & management institutes, and IT professionals.

Rajeev has founded Computer Solutions & Web Services Worldwide. He has hands-on experience of building variety of websites and business applications, that include - SaaS based erp & e-commerce systems, and cloud deployed operations management software for health-care, manufacturing and other industries.


Refer a friendSitemapDisclaimerPrivacy
Copyright © How2Lab.com. All rights reserved.