Page 42 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 3: Recursion

Let’s see how line no. 12 exactly works. Suppose value of i=5, since i is not equal to 1, the Notes
statement:
f = i* factorial (i-1);
will be executed with i=5 i.e.
f = 5* factorial (5-1);
will be evaluated. As you can see this statement again calls factorial function with value i – 1
which will return value:
4*factorial(4-1);
This recursive calling continues until value of i is equal to 1 and when i is equal to 1 it returns 1
and execution of this function stops. We can review the series of recursive call as follow:
f = 5* factorial (5-1);
f = 5*4* factorial (4-1);
f = 5*4*3* factorial (3-1);
f = 5*4*3*2* factorial (2-1);
f = 5*4*3*2*1;
f = 120;

Example 2: Write a C program to find sum of first n natural numbers using recursion.
Note: Positive integers are known as natural number i.e. 1, 2, 3....n
#include <stdio.h>
int sum(int n);
int main(){
int num,add;
printf(“Enter a positive integer:\n”);
scanf(“%d”,&num);
add=sum(num);
printf(“sum=%d”,add);
}
int sum(int n){
if(n==0)
return n;
else
return n+sum(n-1); /*self call to function sum() */
}

The output is given as below:
Enter a positive integer:
5
15
In, this simple C program, sum() function is invoked from the same function. If n is not equal to
0 then, the function calls itself passing argument 1 less than the previous argument it was called
with. Suppose, n is 5 initially. Then, during next function calls, 4 is passed to function and the

LOVELY PROFESSIONAL UNIVERSITY 35