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.
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)); }
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.
#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.
#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.
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)); } }
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
ex = 1 + x + x2/2! + x3/3! + ...
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)
How to move your Email accounts from one hosting provider to another without losing any mails?
How to resolve the issue of receiving same email message multiple times when using Outlook?
Self Referential Data Structure in C - create a singly linked list
Mosquito Demystified - interesting facts about mosquitoes
Elements of the C Language - Identifiers, Keywords, Data types and Data objects
How to pass Structure as a parameter to a function in C?
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.