Sunday 5 October 2014

Recursive Function in C Language

Recursion is a method used to solve some problems where the solution depends on solutions to smaller instances of the same problem. The approach can be applied to types of problems for which solution can be represented recursively.


Most computer programming languages support recursion by allowing a function to call itself from within the body part of the function.

An ideal example of recursion is the solution to find the factorial of a number. Here N factorial is N *  N-1   factorial, and N-1 factorial is N-1 * N-2 factorial and so on. And 1 factorial is 1 itself.

i.e

5! = 5 * 4!
4! = 4 *3!
3! =3 * 2!
2! = 2 * 1!
1! = 1


In this example factorial() function takes a number (n) as argument and returns the factorial of the number. If the number passed is 1 the function returns 1 itself  i.e 1!=1, otherwise the same function will be called with n-1 as argument. It will create a stack of instances of factorial function. Finally when n  becomes one, it starts returning from an instance to the previous instance and performs the multiplication  (n*n-1!) and the final value will be returned to the main function.



Source Code

factorial.c

/* Recursive function to calculate Factorial */

int factorial(int n) {
    if (n<=1)
        return 1;
    else
        return(n*factorial(n-1));
}


void main() {
    int f, n;
    clrscr();
    printf("Enter a value:");
    scanf("%d", &n);
    f=factorial(n);
    printf("Factorial of %d: %d", n,f);
    getch();
}

Output

Enter a value:5
Factorial of 5: 120

1 comment: