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

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.

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

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

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

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.

Collectives™ on Stack Overflow

Difficulty Understanding Recursion on C++

3 Answers 3

1 Comment

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Related