Hi I've got this basic code exercise the code for the c++ program is:
#include <iostream>
#include <string>
int func(int x){
if ( x==0)
return 2;
else if ( x==1)
return 3;
else
return (func(x-1)+func(x-2));
}
int main()
{
std::cout<<func(5)<<std::endl;
return 0;
}
I have compiled and ran this code. The Output is 21.
But I dont understand how the output comes out as 21 can someone please explain.
It works exactly like this non-recursive translation:
int func_0() { return 2; }
int func_1() { return 3; }
int func_2() { return func_1() + func_0(); } // Returns 3 + 2 = 5
int func_3() { return func_2() + func_1(); } // Returns 5 + 3 = 8
int func_4() { return func_3() + func_2(); } // Returns 8 + 5 = 13
int func_5() { return func_4() + func_3(); } // Returns 13 + 8 = 21
int main()
{
std::cout << func_5() << std::endl;
}
You can predict your output by following each step manually. In your case, each func call would work like the following chart:
func(5)
+
+--+ func(4)
| +
| +--+ func(3)
| | +
| | +--+ func(2)
| | | +
| | | +--+ func(1) = 3
| | | |
| | | +--+ func(0) = 2
| | |
| | +--+ func(1) = 3
| |
| +--+ func(2)
| +
| +--+ func(1) = 3
| |
| +--+ func(0) = 2
|
+--+ func(3)
+
+--+ func(2)
| +
| +--+ func(1) = 3
| |
| +--+ func(0) = 2
|
+--+ func(1) = 3
+-----------+
21
As the code is very small, you can predict the output by walking through the program physically, or you could use a debugger to step through.
Main is the entry point of your program; So the very first line that you should start with is std::count<<funct(5)<<std::end1;.
You enter the func(int x) method with an initial parameter x of 5. This function looks at the parameter and returns 2 or 3 if x is 0 or 1, respectively. Otherwise, it will recursively call itself, returning the sum of func(x-1) and func(x-2).
Stepping through you get the following execution order:
func(5)
func(4)
func(3)
func(2)
func(1)
return 3
func(0)
return 2
func(1)
return 3
func(2)
func(1)
return 3
func(0)
return 2
func(3)
func(2)
func(1)
return 3
func(0)
return 2
func(1)
return 3
Which translates to -> 3 + 2 + 3 + 3 + 2 + 3 + 2 + 3 = 21
If you aren't too familiar with recursion in programming, the concept should already be vaguely familiar. You almost certainly have come across the Fibonacci Sequence, where the next number in the sequence is the sum of the previous two (with the first two numbers of the sequence defined as 0 and 1). The program you presented is very similar to the Fibonacci Sequence, however, it uses 2 and 3 as the first two numbers.
Hence, if you define the recursive sequence as a0 = 2, a1 = 3, then an = an-1 + an-2, which looks very similar to the function defined.
It is recursion so I runs like this
func is called with 5
func(4) + func(3)
func(3) + func(2) + func(2) + 3
func(2) + func(1) + func(1) + func(0) + func(1) + func(0) + 3
func(1) + func(0) + 3 + 3 + 2 + 3 + 2 + 3
2 + 3 + 16
21
