Recursion

A function is generally call another function to accomplish the task but sometimes a function can call itself to complete the task. This type of function is known as a recursive function and this feature is known as recursion. Let's take a short example of the recursive function.

main(){
    printf("Hello");
    main();
}

In the above program snippet main() function calls itself so main() is known as recursive function but the output of the above program snippet is "hello" prints indefinitely. The following program snippet improve the above logic and try to make it finite.

main() {
    int i=1;
    if(i<=10) {
    	printf("Hello");
        i++;
        main();
    }
}

1. If you thought that above logic print "Hello" 10 times then you are wrong because when program start i becomes one and of course the condition gets true and "Hello" gets printed then i becomes 2 by increment and then the main() function is again called. As the main() function is again called i again becomes 1 because of initialization. In this way i rotate 1 to 2 and 2 to 1 back and termination never achieved. so the above logic is again indefinite.
2. To make the above logic finite we have to prevent i to reinitialize. This can be done by two way one is that i is declared as a global variable and declared outside the main as given below

int i=1;
main() {
    if(i<=10) {
    	printf("Hello");
        i++;
        main();
    }
}

The next solution is that declare the variable i as a static variable.static variable don't initialize again during the function call.

main(){
    static int i=1;
    if(i<=10){
    	printf("Hello");
        i++;
        main();
    }
}

With the above program snippet it is clear that recursive function has two important parts.

1. Recursive Statement
2. Termination Condition

Lets discuss some other example to grasp over recursion.

Program: To find the factorial of a number using Recursive function

#include<stdio.h>
long fact(int n) {
	if(n==0)
		return 1;
	return n*fact(n-1);
}
int main() {
	int n;
 	long ans;
 
	printf("Enter any number: ");
 	scanf("%d",&n);
 
 	ans=fact(n);
 
	printf("Factorial=%ld",ans);
 	
 	return 0;	
}

Output

Enter any number: 5
Factorial=120

Program Description

In the above program, the fact(n) function is called from main() and jumps to the function definition. The input n gets received by the n in function definition and the function returns a long value so the function is defined as long fact(int n).The fact of how recursive function works can be understood by the following figure. Work with the following figure carefully and try to find the result.

As shown in the above program the recursive function call until it termination is achieved and then the final ans calculate by returning values back to back. The process to go back and calculate the final result is known as backtracking.

Program: To find the sum of digits of a number using recursive function

#include<stdio.h>
int sumdig(int n) {
 	if(n==0)
 		return 0;
	return n%10+sumdig(n/10);
}
int main() {
 	int n,result;
 	printf("Enter any number: ");
 	scanf("%d",&n);
 	
 	result=sumdig(n);
 
	printf("Sum of digits=%d\n",result);
 
	return 0;
}

Output

Enter any number: 347
Sum of digits=14

Program Description

1. Suppose the number is 1234, whose sum of digit you want to calculate. The basic concept in the above program is that if we extract a digit from the above-given number and then add it to the sum of the remaining digits then the final result can be calculated.
2. Now suppose sumdig(1234) is a function which can calculate the sum of the dig of any given number and then extract a digit by performing mod such as 1234%10 returns 4 and then add it to the sum of remaining digits. But how to find the sum of remaining digits? The answer is simply call the sumdig() function with the remaining number. Now Trace the above program and find the fact behind the above logic.