3

I need to write a program that recursively checks if a number is a fibonacci number; It is easy to do this same task iteratively; also it is easy to find the nth fibonacci number recursively, but I'm stuck in how to check wether a number is fibonacci using recursion. here is the code to find the nth fib. number:

int fib(int n){
    if (n <= 1){
       return n;
    }else {
       return (fib(n-1) + fib (n-2));
    }
}

what I don't know how to do is how to modify the above code to check if a given number is fibonacci?

EasyQuestions
  • 327
  • 1
  • 10
  • 23
  • You need an actual test in the function itself and then you need to pass it along. You have the proper function you just need to state your problem to yourself and write down how you would do it on paper and it will come to you. – sean Nov 21 '12 at 06:01
  • Is this a homework? Because there are easier ways to do it without any recursion needed – SingerOfTheFall Nov 21 '12 at 06:02
  • I know you it is much easier to do it iteratively or use the mathematical proof, but it has to be done recursively – EasyQuestions Nov 21 '12 at 06:05
  • 1
    I guess one thing you could do is simply recursively generate the Fibonacci numbers until you got or exceeded the number to test? Not sure if that qualifies as testing recursively though. – Brian L Nov 21 '12 at 06:07
  • there should be a faster way of doing that. also when do you stop the sequence? – EasyQuestions Nov 21 '12 at 06:10

4 Answers4

5

The traditional way is to use Gessel's test. N is a Fibonacci number if and only if 5N2 + 4 or 5N2 – 4 is a square number. This is discussed in this SO question and this SO question. You can also find examples here, but this page has code on Python (though it's easy to understand).

Now, if you were asked to use recursion specifically... Well one way is just so start generating Fibonacci numbers until the generated number becomes more or equal to the number you are testing. If there is a match, the tested number belongs to Fibonacci sequence. If there is no match, and you have generated a number greater than the tested one, then the tested number is not a Fibonacci number.

Here is a basic (and ugly) example for you:

bool isFibonacci( int testedNumber, int a = 1, int b = 1 )
{
    if( testedNumber == 0 || testedNumber == 1 )
        return true;//returning true for 0 and 1 right away.
    int nextFib = a + b;//getting the next number in the sequence
    if( nextFib > testedNumber )
        return false;//if we have passed the tested number, it's not in the sequence
    else if( nextFib == testedNumber )
        return true;//if we have a perfect match, the tested number is in the sequence
    else
        isFibonacci( testedNumber, b, nextFib );//otherwise, get the next fibonacci number and repeat.
}

Use it just as isFibonacci( the_number_you_want_to_test );

Note that Fibonacci numbers can be calculated in O(log n) time, as described for example in this SO question.

Community
  • 1
  • 1
SingerOfTheFall
  • 29,228
  • 8
  • 68
  • 105
  • it has to be done recursively, i guess what my trouble is to how do i store the result each time a recursive call is made, because in recursion the result is not calculated until it is reached the base case. – EasyQuestions Nov 21 '12 at 06:13
1

This feels a bit clunky to me, but you could try:

bool isFib(int numToCheck int twoPrev = 0, int prev = 1) {
    if (numToCheck == twoPrev || numToCheck == prev)
        return true;

    int currentFibNumber = twoPrev + prev;
    if (currentFibNumber == numToCheck)
        return true;
    else if (currentFibNumber > numToCheck)
        return false;

    return isFib(numToCheck, prev, currentFibNumber);
}

This basically iterates Fibonacci numbers using recursion until either the generated number exceeds the value you're checking or a match is found.

As other's have pointed out, there are solutions to this that do not require recursion.

kevintodisco
  • 5,061
  • 1
  • 22
  • 28
  • thank for posting, but this requires to pass the " two previos numbers" to the function when called for the first time. right? – EasyQuestions Nov 21 '12 at 06:17
  • @EasyQuestions Not when you declare them as optional arguments, as I have. An initial call like `isFib(144);` will suffice. – kevintodisco Nov 21 '12 at 06:19
0

Determining whether a number is a Fibonacci number looks like the same thing, but in Java - you could probably get what you're looking for there.

Community
  • 1
  • 1
Krease
  • 15,805
  • 8
  • 54
  • 86
0

Fibonacci numbers have a mathematical property. A number is Fibonacci if and only if one or both of (5*n^2 + 4) or (5*n^2 – 4) is a perfect square (Source: Wiki).

This method is much simpler than recursive function calling method. Check this link:

http://www.geeksforgeeks.org/check-number-fibonacci-number/

Another method:

static bool IsFib(long n)//n is the number to be checked
{
    double root5 = Math.Sqrt(5);
    double phi = (1 + root5) / 2;

    long idx    = (long)Math.Floor( Math.Log(n*root5) / Math.Log(phi) + 0.5 );
    long u = (long)Math.Floor( Math.Pow(phi, idx)/root5 + 0.5);

    return (u == n);
}

This code works for large inputs. It was posted by abelenky in stackoverflow for a similar question.

LoveToLearn
  • 11
  • 2