CODEWITHSUNDEEP
c++recursion
jfelix-agda
jfelix-agda

Reputation: 27

Difficulty Understanding Recursion on C++

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

92

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.

Upvotes: 0

Views: 188

Answers (3)

Jimm
Jimm

Reputation: 15

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.

Upvotes: 0

i_am_human_probably
i_am_human_probably

Reputation: 91

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);
}

Upvotes: 0

Aplet123
Aplet123

Reputation: 35560

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.

Upvotes: 1

Related Questions