TRENDING TOPICS

×

C Recursion

A Function calling itself is called as a recursive function and this process called as recursion.

In C Programming, Recursion plays a very important role in solving some very complicated problems but it becomes very important to manage recursion very carefully otherwise it can cause big issue like memory out of bound.

Recursion in C

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 in c

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

Advertise With Us

We offer sponsored posts and guest posts with do-follow links, back-links, and other advertising services, To advertise email us at "advertise@gdatamart.com"

© 2021 GDATAMART.COM (All Rights Reserved)