Can someone explain to me how exactly this program works?

[ElectricCowBoy]

I know it goes through the Fibonacci sequence listing 16 Fibonacci numbers, more specifically I want to know, how this program works, exactly how the compiler would execute this, the flow/logic behind it, the part that confuses me, is this part: fibonacci(n - 1) + fibonacci(n - 2), I don't get what happens when you reference the function inside of the same function, does it simply go through the function again with those parameters? If so how does it do that when those two declarations are summed together? Some kind of precedence?
Thanks.

#include <iostream>

#include<conio.h>
using namespace std;

int fibonacci(int n)
{
	return (n <= 2 ? 1 : fibonacci(n - 1) + fibonacci(n - 2)); 
}

int main(void)
{
	for (int n = 1; n <= 16; n++)
		std::cout << fibonacci(n) << ", ";
	
	_getch();
	return 0;
}

[Zhuge]

Yes, that's exactly what it does. It just calls the function again with those parameters and calculates the result. There is some precedence, in that the addition can't be completed until the two addends (i.e., results of the calls) are calculated, but I'm not sure what you mean by "how does it do that?"

It's actually just as simple as you said; the function just gets called again. The fact that it happens to be the same function that you are already in doesn't affect that.

[ElectricCowBoy]

I get it! I was forgetting about the return statement for a minute there. Thanks!

[axtyax]

Just curious about what the ? and : operators are doing here

[axtyax]

In other words what is their purpose

[keskiverto]

They are the ternary operator.

[axtyax]

ahh thanks, i'll look into it

[ElectricCowBoy]

I have another question about this, if the function is again called with those parameters, like Zhuge said, and the condition is not met, falling to the else part of the function, where fibonacci(n - 1) + fibonacci(n - 2), because that is the same as before, will it just call the function recursively until the first condition is met? ( n <= 2 ? 1), or is there a rule that specifies that it can only be called once, until the two numbers are summed and returned, resulting in cout?

I want to be able to go back through the program and work out what will be cout to the screen before, it is actually outputted, using the function described above.

[Zhuge]

It will continue to call them as long as the logic dictates they should. It can't return after being called only once because then, in the case of fib(4), you would need to add the results of fib(3) and fib(2), which can't be found out if you don't call them. Eventually, since the parameter n is decreasing each call, you will eventually stop recursing when you drop less than or equal to 2.

You may find it useful to look at this function in this way, supposing we start with fib(4):
fib(4)
fib(3) + fib(2) [expand fib(4)]
fib(3) + 1 [expand fib(2)]
fib(2) + fib(1) + 1 [expand fib(3)]
1 + fib(1) + 1 [expand fib(2)]
1 + 1 + 1 [expand fib(1)]
2 + 1 [addition]
3 [addition]

[ElectricCowBoy]

How can this sequence be archived then if n is getting incremented by 1 each time, surely the code only permits numbers below or equal to 3 as you said, because the other part of the function would decrease it to a level in which that comparison is true? I'm confused about this, maybe I'm getting something wrong along the lines of what n is actually equal to? like when the value of n is returned does that change the value of n? inside of the for loop?

[xismn]

How can this sequence be archived then if n is getting incremented by 1 each time, surely the code only permits numbers below or equal to 3 as you said, because the other part of the function would decrease it to a level in which that comparison is true?

Keep in mind - if I understood you correctly - that it's very possible for the sum of two numbers smaller or equal to 2 to be larger than 2.

for n = 1 :
return	1 because 1 is less than or equal to 2.



for n = 2 :

return	1 because 2 is less than or equal to 2.



for n = 3 :

return	f(3 - 1) + f(3 - 2)

	which is

	f(2) + f(1)

	which is 

	1 + 1

	the result is 2



for n = 4 :

return	f(4 - 1) + f(4 - 2)

	which is

	f(3) + f(2)

	the first term evaluates to 2, as described just above

	the second term evaluates to 1

	the result is 3

...