I'm having a hard time understanding why
#include <iostream>
using namespace std;
int fib(int x) {
if (x == 1) {
return 1;
} else {
return fib(x-1)+fib(x-2);
}
}
int main() {
cout << fib(5) << endl;
}
results in a segmentation fault. Once x gets down to 1 shouldn't it eventually return?
In mathematics, things are often defined recursively. For example, the Fibonacci numbers are often defined recursively. The Fibonacci numbers are defined as the sequence beginning with two 1's, and where each succeeding number in the sequence is the sum of the two preceeding numbers.
The method fib() calculates the fibonacci number at position n. If n is equal to 0 or 1, it returns n. Otherwise it recursively calls itself and returns fib(n - 1) + fib(n - 2).
Fibonacci Trees. This exercise deals with "Fibonacci trees", trees that represents the recursive call structure of the Fibonacci computation. (The Fibonacci sequence is defined as follows: F0 = 0, F1 = 1, and each subsequent number in the sequence is the sum of the previous two.)
The reason is because Fibonacci sequence starts with two known entities, 0 and 1. Your code only checks for one of them (being one).
Change your code to
int fib(int x) {
if (x == 0)
return 0;
if (x == 1)
return 1;
return fib(x-1)+fib(x-2);
}
To include both 0 and 1.
When x==2
you call fib(1)
and fib(0)
:
return fib(2-1)+fib(2-2);
Consider what will happen when fib(0)
is evaluated...
Why not use iterative algorithm?
int fib(int n)
{
int a = 1, b = 1;
for (int i = 3; i <= n; i++) {
int c = a + b;
a = b;
b = c;
}
return b;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With