Recursion Function

Recursive function is one of the most powerful programming technique. In this the function calls itself during the execution. It helps in providing simple solutions to difficult problems. Many difficult programs can be written efficiently using recursive algorithm.

Factorial Function

Take the case of the factorial function. The factorial function is written mathematically as

$$n! = \begin{cases} 1, & n=0 \\ n(n-1)!, & n>0 \end{cases} $$

This is a recursive function because the function calls itself on the right side of the equation. In the form of code, it can be written as

long fact(int n){
    if(n<2){
        return 1;
    }
    else{
        return n*fact(n-1);
    }
}

This code calls the function itself with the one less value than the original. Lets trace the call of fact(4). The call starts from main function, it calls fact(4). 4 is passed to the fact() function. Now this function needs the value fact(3), so 3 is passed to fact() function, which calls fact(2). Now the call is made from fact(2), which calls fact(1). Finally, fact(1) return 1. Then the call fact(2) return 2*1 = 2. This value is used in fact(3). The call fact(3) returns 3*2=6. Then the value fact(4) returns 6*4=24. So the value of factorial accounts to 24, which is the final value of factorial 4.

We can write the same program in the non-recursive way as and test if the results are same for both the codes.

long fact2(int n){
	long a = 1;
	for (int i=2;i<=n;i++){
		a*=i;
	}
	return a;
}

Many problems can be simplified using recursion function, we see below in two of the recursion functions for simple problems.

Recursive function to find $x^n$

long power(int x, int n){
	if (n==0){
		return 1;
	}
	else{
		return x*power(x,n-1);
	}
}

The function defined above is the power function to find the nth power of x. The recursion starts and the value of power keeps on decreasing by 1. The recursion ends when the power reaches 0, and the value of 1 is assigned to the earlier function, as defined in the factorial function. The value x is then multiplied each time and passed on to the calling function. So at last we get the value of $x^n$.

Recursive function to find sum of the first n elements of an array.

int sum(int a[], int n){
	if(n==0){
		return 0;
	}
	else{
		return a[n-1]+sum(a,n-1);
	}
}

We see that the function calls itself until it reaches the last number. It then calls 0 and returns to the last called function. The updated value is then returned and same continues till the value of n is reached. The same function can be written in the loop format as

int sum2(int a[], int n){
	int sum = 0;
	for(int i=0;i<n;i++){
		sum = sum + a[i];
	}
	return sum;
}

Both the functions output the same value. You can also try to write various programs given below as problems for recursive function.

Leave a Reply