C recursion problems

Question

I have a query regarding a recursive function. This is my program.

#include <stdio.h> int fun(int); int main(void) { int x; int k=3; x = fun(k); printf("%d\n",x); return 0; } int fun(int a) { int f; if(a == 1) return (1); f = 2 + fun(a-1); return (f); } 

where I have a K=3 value in STEP-6 . In STEP-7 , the fun(k) function passes the K value of the called function to STEP-11 int fun(int a) . In the fun(int a) function called, recursion occurred 2 times, i.e. (3.2) by making the value a=1 . Which later in STEP-14 value of f becomes 3, since f = 2 + (fun (1) = 1). In STEP-16 it returns to the function called ie fun(int a)=3 . Which should print the value of x is 3 , it is unlikely that this is not the case. This is x = 5

Answer 1

Let the calling sequence fun() be checked, will we?

With an argument value of 3 , starting with main()

• x = fun(3)
  • f = 2 + fun(2);
    • f = 2 + fun(1);

Now let's check the return values ​​only in reverse order.

• The last call to fun(1) returns 1 ,
• So the second call to fun(2) returns 2 + 1 or 3 ,
• The last call to fun(3) returns 2 + 3 or 5

and this is a call from main() . So, in main() , x gets the value 5 .

Answer 2

The fun(3) score is as follows:

 fun(3) 2 + fun(3-1) 2 + fun(2) 2 + 2 + fun(2-1) 2 + 2 + fun(1) 2 + 2 + 1 5 

From your description, I think you have some misconceptions about clouds in C (and recursion in general). The fact that f assigned the value 3 inside fun(2) does not mean that the value of f in the fun(3) changes - they are completely separate variables.

Answer 3

For recursive functions, it is generally recommended that you draw a recursion tree to better visualize what is happening.

• f (3) will call f (2), f (2) will continue to call f (1), which is basic.

• f (1) will return 1. Now f (2) will return 2 + 1 = 3.

• f (3) will now return 2 + 3 = 5.

Check out the recursion tree below:

  |------> returns (2 + 3) = 5 | f(3)<--- | | | | returns (2 + 1) = 3 f(2)<--- | | returns 1 | | f(1)---- (This is the base case. No further recursion. It returns 1). 

Answer 4

I see there a lot of good answer already published. However, I am posting this answer, which may help you in the future when you engage in more complex recursion.

Whenever you find something about recursion, try mathematically solving it first on your laptop. A good approach starts with the base case.

The base block of the fun(k) function is fun(1) , which returns 1 . So start with the following:

 fun(1) = 1 // let read this, function fun(1) returns 1 

Now for fun(2) , what will happen?

 fun(2) = 2 + fun(1) = 2 + 1 // we already calculated fun(1) =1 = 3 fun(3) = 2 + fun(2) = 2 + 3 // we already calculated fun(2) = 3 = 5 

I think it now makes sense why x = 5 !