Fibonacci got different outputs

Question

I tried to find the nth fibonacci number. But if i enter 0(zero) as input why does it give 0 as output for the for loop and 1 for the recursion?

The code:
#include<bits/stdc++.h>
using namespace std;

int f(int n)
{
if(n <= 1) return n;
int last = f(n-1); /// THIS WILL BE EXECUTED FIRST // f(1) may be called many times
int slast = f(n-2);/// THEN THIS WILL BE EXECUTED
return last + slast;
}
int main()
{
cout << "Multiple recursion calls" << endl;
int n;
cin >> n;
int fibo[n];

fibo[0] = 0;
fibo[1] = 1;
for(int i = 2; i < n; i++){
fibo[i] = fibo[i-1] + fibo[i-2];
}

cout << "The nth fibonacci number is " << fibo[n-1] << " or " << f(n)<< endl;

return 0;
}

Answer 1

I get 0 as output for both when I enter 0 as input. But I get different answers when I enter 1. This is because you are showing fibo[n-1] in your output.
fibo[1-1] = fibo[0] = 0
which is wrong. You just need to do fibo[n]

The problem with that is that when n=0, you will be making an array of size 0, and fib[0] will be invalid. Better to make an array with (n+1) elements.

Also, (unrelated to the fibonacci issue) the array you are making is a variable-length array (VLA), and they are not allowed in the C++ standard. The reason it works is because GCC provides an extension for VLAs. It's better to not use them. The length you provide to the array must be constant
int arr[10]; // OK

int n;
cin >> n;
int arr[n]; // WRONG

It's better to
1. Make an array with a "long enough" but constant length
2. Allocate some memory
int* arr = new int[n];
3. Create a std::vector

Answer 2

Your function is actually irrelevant to nth number finding. You need find nth element in array but you never using array in function. If you use array, then it simply the last element just. So first need to pass array then return the n-1 th element...
what else your idea actually there?

edit:

ok. understood fine. you are going with recursion. another way...
you can simply do like

if( n<= 1) return n;

return f(n-1) +f(n-2) ;

Answer 3

You never call your function f in the main, you use only [ ] instead of ( )

Answer 4

Jayakrishna🇮🇳
"but you never using array in function"
What do you mean by this? I think the OP is trying to explore 2 different ways of finding fibonacci numbers, or am I understanding the question wrong?

Answer 5

XXX
Fibonacci numbers are in fibo[] array. And there is no relation of with function. Oh. May be , is it another approach of finding it by recursion? Then I should look at it again.., fine if you are already mentioned about it.

It will return either 1 or 2 or 0 always, I think .

Answer 6

The base case should return 1 and not n

Answer 7

Yeah 0 not 1, I was thinking about n being a negative number

Answer 8

Swapnil
Your approach differs because in array way, you are displaying n-1 element but with recursive way, displaying nth element.

And VLA not recommended, but you can try here arr[2+n] to not crash for input 0. So call as f(n-1) instead.
and add cache if( n<0) return 0; first

Answer 9

Kenobi
it shouldn't. f(0) should be 0, not 1

Answer 10

Fibonacci sequence is the classic example of recursion where each term is the sum of the previous two ✌ j.e. 0 1 2 3 5 8 13.

Factorials are another great example eg. 5 ! = 5*4*3*2*1 ..
Here there are two scenarios: F(n) * F(n-1) for n >=2 ELSE 1.

Answer 11

In the recursive function f(), the base case is when n <= 1, in which case it returns n. This means that when n is 0, the function returns 0.

On the other hand, in the for loop, the base case is when i = 0. In this case, fibo[0] is assigned the value 0, and fibo[1] is assigned the value 1. The loop then starts at i = 2, so fibo[2] is assigned the value of fibo[1] + fibo[0], which is 1.

This is why you are getting different outputs for n equal to 0. In the recursive function, n is the input and the function returns n when n is 0 or 1. In the for loop, i is the loop variable, and fibo[0] is assigned the value 0 and fibo[1] is assigned the value 1.

Answer 12

https://code.sololearn.com/caZo8Yjy1KP6/?ref=app

Answer 13

Thanks everyone 🥰