Difficulty Understanding Recursion on C++

Question

I have this example block of code that I tried to replicate, a recursive function for finding Fibonacci numbers

#include <iostream>

using namespace std;

int fibonacci(int n)
{
if (n==0)
 return 0;
else if (n==1)
 return 1;
else return fibonacci(n-1)+(n-2);
}

int main()
{
cout<<fibonacci(15);
}

the following example outputs

when executed.

Looking at some examples now, I see that the formula is wrong, but I am still curious as to why the output is what it is, as I have been having a hard time trying to understand how recursion works.

Tip: draw a recursion tree on a piece of paper to find out how it works. — Asesh
– Asesh, Commented Dec 1, 2020 at 2:37
If you use a debugger to step through the code, it will help you understand how recursion works pretty quickly. So would putting a cout<<n at the beginning of your fibonacci() function. — Ken White
– Ken White, Commented Dec 1, 2020 at 2:37
1) What's unclear about recursion? fibonacci(n-1)+(n-2); is equivalent to fibonacci(n-1) + n - 2; So, it's basically equal to 15 + 14 + 13 + 12 + 11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 - 2 * 14, or in more general terms: sum (n) - 2 * (n - 1) What's unclear about that? — Algirdas Preidžius
– Algirdas Preidžius, Commented Dec 1, 2020 at 2:38
This is the perfect time to learn about how the stack works. — paddy
– paddy, Commented Dec 1, 2020 at 2:40

Aplet123 · Accepted Answer · 2020-12-01 02:37:46Z

1

You should be adding the previous two fibonacci numbers, so fibonacci(n - 1) + fibonacci(n - 2), not fibonacci(n - 1) + (n - 2), which lacks a function call. With fibonacci(n - 1) + (n - 2), you simply add n - 2 to the previous term in the series, giving you a series similar to triangular numbers.

answered Dec 1, 2020 at 2:37

Aplet123

35.8k1 gold badge41 silver badges66 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

paddy Over a year ago

Should probably be noted that this has exponential time complexity, and is one of the most computationally expensive ways to actually calculate Fibonacci numbers. Something as simple as fibonacci(42) results in just shy of one billion recursive calls.

i_am_human_probably · Accepted Answer · 2020-12-01 02:46:11Z

0

Like the other user posted, you're missing the function call for the (n-2) portion.

As far as how recursion works, think of it like a tree. For each function call, your current state on the stack is saved, and you move your program counter to the function call; it just so happens to be that it's also the current function you are in. When you get to the bottom of the tree, you'll unwind the stack.

This returns the correct answer:

#include <iostream>

using namespace std;

int fibonacci(int n)
{
if (n==0)
    return 0;
else if (n==1)
    return 1;
else 
    return fibonacci(n-1)+fibonacci(n-2);
}

int main()
{
    cout<<fibonacci(15);
}

answered Dec 1, 2020 at 2:46

i_am_human_probably

811 silver badge8 bronze badges

Comments

Jimm · Accepted Answer · 2020-12-01 04:00:27Z

0

It'd be this

#include <iostream>
using namespace std;

int fibonacci(int n)
{
  if (n==0) //base case
    return 0;
  else if (n==1) //base case
    return 1;
  else return fibonacci(n-1)+ fibonacci(n-2);
}

int main()
{
    cout<<fibonacci(15);
}

When you first call the fibonacci function, fibonacci(n-1) + fibonacci(n-2) means fibonacci(14) + fibonacci(13). The recursion happens, the next pass will be fibonacci(13) + fibonacci(12) and fibonacci(12) + fibonacci(11) respectively. The recursion processes will continue with this manner until it hits one of the base cases, the recursion will then stop and start to return values.

answered Dec 1, 2020 at 4:00

Jimm

156 bronze badges

Collectives™ on Stack Overflow

Difficulty Understanding Recursion on C++

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related