What is output..?
In above program the function main() is a recursive function, because it’s calling itself, so what do you think about output of program.
Output
Program will give an error as memory out of bound
Explanation
- When program first loads in memory, a memory frameset created and reserved on stack for main() function.
- When main() function executes a new frameset created to reserve space for main() function, this process executed until stack memory not filled. When there is no more space available in stack memory then program generates error like memory out of bound. See below image
Recursion Example 1
Output
Error
mrmory out of bound
Explanation
In above program hello() function is a recursive function because it’s calling itself.
Use recursion with conditions
- It is best practice to use recursion with condition statement like if, if else etc.
- In this way we can solve some very complicated problems very easily, let’s see some best use of recursion.
Program 1 : Sum of first n natural numbers
Lets write a program to find sum of first n natural numbers using recursion with conditions.
Output
Enter number of first natural numbers to find their sum
3
sum of first 3 natural numbers is 6
Explanation
Above program will calculate the sum of first n natural numbers. In this program we are using recursion concept with condition, so let’s understand execution of program.
Step 1:
main() function will start execution and it will ask input from user, user enters 3 as input which is stored in variablen, now myfun() function called in main() function and n passed as a parameter of function.
Step 2:
myfun() receive passed parameter value from main function which is 3 in variable a. A block space for myfun() created in stack memory. The first line in myfun() executed which is if condition a==1, this condition fails because the value of a is 3 right now. So next line executes which is sum + myfun(a-1) , means myfun() calling it self with parameter value 2, since current value of a is 3 but we are passing a-1 means 3-1=2.
Step 3:
Since myfun() again called itself in step 1 with parameter value 2, so again a new block of space in stack memory created and variable a is assigned with value 2, now the first line of function myfun() which is if(a==1) executes but it is false because the value of a is 2 right now. So next line executes which is sum+myfun(a-1), means myfun() calling itself again with parameter value 1, since value of a is 2 but we are passing a-1 means 2-1=1. Currently step 2 is waiting for myfun() return value.
Step 4:
myfun() called from step 3 with parameter value 1, so gain myfun() function will executes, the value of a is assigned by 1. First line of function executes which is an if condition of a==1, this time it is true and this function return the value of a which is 1 in this case. Now 1 returned to step 3 from step 4.
Step 5:
In step 3 the value of a+myfun(a-1) will be calculated where the value of myfun(a-1) is 1 which is returned from step 4. In step 3 the value of a is 2 so a+myfun(a-1) is 2+1=3 and it is stored in variable sum. The value of sum in step 3 is 3. Now value of sum returned to step 2.
Step 6:
In step 2 the value of a is 3 and the value returned by function myfun() from step 3 is 3, means in step 2 the value of myfun(a-1) is 3 so complete result of a+myfun(a-1) is equal to 3+3=6 so in step 2 value of variable sum is 6 and step 2 return this value to the step 1
Step 7:
In step 1 the value of myfun(n) is 6 which is returned from step 2, now 6 assigned as the value of variable res in step 1 and it is the value of printed on output.
Program 2: Factorial of a Number
Lets write a program to find factorial of a number numbers using recursion with conditions.
Output
Enter a number to find it's factorial
4
Factorial of 4 is 24