### about recursion function

so I've been reviewing function and I wondered if you guys could help me with something , my question is , when will the computer know where to stop ? in this code here ..

 ``1234`` `````` if (( number == 0 )||( number == 1 )) return number; else return fibonacci( number - 1 )+ fibonacci(number - 2 );``````

I know that it's going to call fibonacci( number - 1 ) first , for example if number = 4; then it's going to call fibonacci(3) and then 2 and stops at one , but what's the value that it's going to return ? I'm really lost :(
For number at value 4:
`if (( number == 0 )||( number == 1 ))`
The if evaluates to false, so the body of the if is not executed.
Instead, the body of the else is executed.
`return fibonacci( number - 1 )+ fibonacci(number - 2 );`
This else body starts with the keyword `return` so whatever value is calculated on the right hand side of the return up to the semicolon will be the value returned for the function this code is in.
(I am going to assume this code is inside the fibonacci function.)
So on with the value that is going to be calculated...
`fibonacci( number - 1 )+ fibonacci(number - 2 )`
There are two function calls here and c++ will probably execute `fibonacci( number - 1 )` first. What happens at this moment is your computer will remember that it was at the '+' sign, then it will execute `fibonacci( number - 1 )`. (The remembering is done by something called a stack.)

So far:
The else was executed and the computer remembered it was at the plus sign. Now it uses number at value 3, since 4 - 1 is 3. Once again the if statement is false and does the else again. The computer will remember a second plus sign and do another function call to `fibonacci( number - 1 )`. This second plus sign goes to the top of the stack, so that is above the first plus sign. This means the second will happen before the first later when the computer retraces steps.

With number at value 3, basically 3-1 is 2:
 ```fibonacci( 2 ) '+' #2 '+' #1```

That is the top of the stack.

Skipping forward:
 ```fibonacci( 1 ) '+' #3 '+' #2 '+' #1```

Now when fibonacci(1) runs the if statement will be true.
`return number;` is executed.

Stack now has a number to return:
 ```1 '+' #3 '+' #2 '+' #1```

So the computer decides it should retrace steps now and stick the one to the left of the plus sign. And at the third plus sign number's value was 2, so:
 ```'1 + fibonacci((2) - 2 )' #3 '? + fibonacci((3) -2)' #2 '? + fibonacci((4) -2)' #1```

 `fibonacci((2) - 2 )`
is going to return 0 since number will be value 0 and the if will be true, which just returns number.
 ```'1 + 0' #3 '? + fibonacci((3) -2)' #2 '? + fibonacci((4) -2)' #1 ```
 ```'1' #3 '? + fibonacci((3) -2)' #2 '? + fibonacci((4) -2)' #1```
 ```'1 + fibonacci((3) -2)' #2 '? + fibonacci((4) -2)' #1 ```
 ```'1 + 1' #2 '? + fibonacci((4) -2)' #1```
 ```'2' #2 '? + fibonacci((4) -2)' #1```
 `'2 + fibonacci((4) -2)' #1`
 ```'fibonacci(2)' #2 '2 + ?' #1```
 ```'fibonacci(1) + fibonacci(0)' #2 '2 + ?' #1```

A little skipping ahead and you have:
 `'2 + 1' #1`

Recursion always stops when the function quits calling themselves.
Someone once told me, "To understand recursion you need to understand recursion."
Thank you so much , I'll review what you said and try to understand it , if I got any question I'll post them here ,

I was aware of the stacking thing " basics " which does something and then get rid of it ,

anyways thanks a lot
Topic archived. No new replies allowed.