Why doesn't my fibonacci search work?

Hello?

I was messing around with the fibonacci sequence and it's implementation and I got the hang of it.
And I want to find which number from the fibonacci sequence is bigger than the one given but the problem is if it's a fibonacci number there's a logical error

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
unsigned fib(unsigned k)
{
	if (k == 0)return 0;
	else if (k == 1)return 1;
	else return fib(k - 1) + fib(k - 2);
}

unsigned which_fib( unsigned i, unsigned k=0 )
{
	if (fib(k) < i)
		return which_fib(i, k+1);

	if (fib(k) > i)
		return k;
}

int main()
{
	std::cout << which_fib(8) << "\n";/*<-this outputs 8 when it should
output 7*/

}


Can anyone tell me where is the problem please?

Thank you!
You have no branch for == in which_fib, so it drops through and returns garbage (your compiler should warn you about that possibility).
So the first test needs to be <=, and the second should just be an else.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//     n : 0 1 2 3 4 5 6  7  8  9 10
// fib(n): 0 1 1 2 3 5 8 13 21 34 55

#include <iostream>

typedef unsigned long ulong;

ulong fib(ulong k) {
    return (k < 2) ? k : fib(k - 1) + fib(k - 2);
}

ulong which_fib(ulong i, ulong k = 0) {
    return (fib(k) > i) ? k : which_fib(i, k + 1);
}

int main() {
    std::cout << which_fib(8) << "\n";
}
The compiler didn't warn me...

Still Thank you!
If the compiler didn't warn you then you need to turn up the warning level. In gcc and clang you can add the -Wall flag (as well as the -Wextra and -pedantic flags). Look up how to do it for other compilers. The warnings are really helpful.
Topic archived. No new replies allowed.