CODEWITHSUNDEEP
c++crecursion
Shivaraj Bhat
Shivaraj Bhat

Reputation: 847

C/C++ function recursion

I have been trying to understand the below code snippet,but not quite getting the logic behind the output.

int Func(int x, int y){
    if (x < y)
        return 0;
    else
        return Func(x - y, y) + 1;
}

int main()
{
    int x = 50, y=10;
    printf("%d  \n",Func(x,y));
    return 0;
}

The output for the above program is obviously 5. Can anyone tel me what "+1" (in return Func(x - y, y) + 1;) in the recursion type method actually means and how it have a execution flow.?

If i just execute return Func(x-y,y); then the output is 0, that is fine. But why the output is 5 in the first case?

Upvotes: 3

Views: 217

Answers (5)

Sly_TheKing
Sly_TheKing

Reputation: 528

Just analyze how code goes. First you go down to basic case (just calling the function). Now you called function five times, each time are different arguments. When x < y, you go back and result you return is 0. Remember that you went down 5 times and done nothing but changing the parameters. Now each time you return back, you add +1 to that result, so first time u go back you add +1 and you get 0+1 = 1, then second time you go back you add +1 to that result adn you get 1+1=2, next time 2+1 =3 and so on.

Upvotes: 1

Topological Sort
Topological Sort

Reputation: 2787

Here's what it does. I use . to force an indent, to make it easier to see which recursive call we're in.

You call Func(50, 10).

.This calls Func (40, 10).

..This calls Func (30, 10).

...This calls Func (20, 10).

....This calls Func (10, 10).

.....This calls Func (0, 10). Since 0 < 10, it returns 0.

.....Func(0,10) returned 0. Add 1 to it and return that.

....Func(10,10) returned 1. Add 1 to it and return that.

...Func(20,10) returned 2. Add 1 to it and return that.

..Func(30,10) returned 3. Add 1 to it and return that.

.Func(40,10) returned 4. Add 1 to it and return that.

Func(50,10) therefore returned 5.

So, essentially, the result 5 means the number of recursive calls it made, which is 5.

Upvotes: 2

Matthew Read
Matthew Read

Reputation: 1861

In the base case, Func() returns 0.

If it recurses once, it returns 0 + 1 = 1 (the base case plus 1).

If it recurses twice, it returns (0 + 1) + 1 = 2 (the base case, plus the 1 case, plus 1).

And on and on. Thus, the return value represents how many times the function calls itself, which (as another answer says) computes division ignoring the remainder.

Upvotes: 1

md5
md5

Reputation: 23699

Recursion will proceed as follow:

Func(x = 50, y = 10) x >= y 
  Func(x = 40, y = 10) x >= y
    Func(x = 30, y = 10) x >= y
      Func(x = 20, y = 10) x >= y
        Func(x = 10, y = 10) x >= y
          Func(x = 0, y = 10) x < y
          return 0
        return Func(x = 0, y = 10) + 1 = 1
      return Func(x = 10, y = 10) + 1 = 2
    return Func(x = 20, y = 10) + 1 = 3
  return Func(x = 30, y = 10) + 1 = 4
return Func(x = 40, y = 10) + 1 = 5

Where +1 is used to say: "add 1 to the result computed by Func(x - y, y) in a recursive call".

Upvotes: 9

A. Abramov
A. Abramov

Reputation: 1865

Division is a great substraction, in the end of it. That's the concept this method is showing. Anyhow, The idea here is that the function substracts the second parameter from the first one each time, and adds to the total sum 1. This way, you check how many times does the first parameter fit inside the other, or in other words, substract. (:

Just explaining the specific +1 part:

In the end , the function returns a zero - when the first parameter is below zero. This way, you know when to stop.

Each time you substract, you add one to the total sum of division, which is the return value in each iteration.

Upvotes: 2

Related Questions