Recursive Fibonacci code

Question

I have written the Fibonacci series as below. I would like to like to know if the below is the right way of using recursion because I am thinking I am looping the fibonacci function with the condition and incrementing value of i everytime just like a for loop.

public class FibanocciSeriesImpl {
static int a,b,i,n;
    static
    {
        a=0; b=1;i=2;
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter the number of elements in the series");
        n=sc.nextInt();

    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("The fibnocci series is below");
        System.out.print(a+","+b);
        fibnocciImpl(a,b);
    }
    public static void fibnocciImpl(int a,int b)
    {
        int c=a+b;
        a=b;
        b=c;
        i++;
        System.out.print(","+c);
        if(i<n)
        fibnocciImpl(a,b);

    }
}

This is not the classical implementation of a recursive function for the fibonacci sequence but by definition since you are calling the function within itself it is recursion — Blake Lockley
– Blake Lockley, Commented Mar 27, 2016 at 10:34

MeetTitan · Accepted Answer · 2016-03-27 10:40:22Z

8

The fibonacci sequence can be implemented recursively in two lines of code, like so:

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

Please note this is not the most efficient way of calculating the fibonacci sequence, although this may be the most straightforward code-wise. I'll leave it to you to implement more efficiently.

edited Mar 27, 2016 at 10:40

answered Mar 27, 2016 at 10:34

MeetTitan

3,5851 gold badge16 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

blazs · Accepted Answer · 2016-03-27 10:46:14Z

4

Although this has been said many times, it's worth repeating: computing the Fibonacci sequence recursively---by the definition and without using, say, memoization---takes exponential time (something like O(1.6^n)), which is not feasible for large n (e.g. for n>40).

The Fibonacci sequence can also be computed iteratevly in linear time:

public static long fib(int n) {
    long a = 0, b = 1;
    if (n <= 1) { return n; }
    for (int i = 2; i < n; ++i) {
        int tmp = b;
        b += a;
        a = tmp;
    }
    return b;
}

For what it's worth, here's the same algorithm in Brainfuck (from my high school days :-):

++++++++++ > + ; N i j 
< ; point to N 
[
    > ; move pointer to i
    [ >> + > + <<< - ] ; add i to t1 and t2
    > ; move to j
    [ < + > - ] ; add j i 
    >> ; move to t2
    [ << + >> - ] ; add t2 to j 
    < ; move to t1
    [ >> + << - ] ; add t1 to t3
    >> ; move to t3 
    [ < + < + >> - ] ; move t3 to t1 and t2
    <<<<< -
]
>>> .

edited Mar 27, 2016 at 10:46

answered Mar 27, 2016 at 10:38

blazs

4,85528 silver badges38 bronze badges

4 Comments

marstran Over a year ago

The most naive recursive way may take exponential time, but it can be implemented recursively in linear time as well.

blazs Over a year ago

@marstran sure, what I meant, of course, was that computing by the definition (and without memoization) takes exponential time.

marstran Over a year ago

Here's a recursive solution in linear time without memoization (in Scala because of space): def fibonacci(first: Int, second: Int, n: Int) = if (n <= 0) first else fibonacci(second, first + second, n - 1).

blazs Over a year ago

@marstran, nice, I'm aware of these simple facts. I was merely pointing out that the partricular recursive function that the OP is using takes exponenital time.

Maytham Fahmi · Accepted Answer · 2016-03-27 10:44:07Z

1

It is also possible to implement Fibonacci using Dynamic Programming which is much efficient than recursive.

int fibonacci(int n) {

    int[] f = new int[n + 1];
    int i;

    f[0] = 1;
    f[1] = 2;

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

    return f[i - 2];
}

Time Complexity: O(n) Extra Space: O(n)

answered Mar 27, 2016 at 10:44

Maytham Fahmi

33.2k17 gold badges132 silver badges159 bronze badges

2 Comments

Paul Boddington Over a year ago

There's no reason to create an array if you only ever use the last two values. Two local variables will do.

Maytham Fahmi Over a year ago

@paulboddington I agree with you, but it is just to demonstrate the possibility for OP,

FoldFence · Accepted Answer · 2016-03-27 11:19:32Z

0

You can do it in recursive like:

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

But the faster way is to do it with the iterativ way as you can read with examples here:

Iterative vs Recursive

answered Mar 27, 2016 at 11:19

FoldFence

2,8005 gold badges36 silver badges58 bronze badges

Comments

Sameh · Accepted Answer · 2016-03-27 11:45:12Z

Yes it's recursion, and no it's not recursion. :)

It's recursion because you are calling the function again, but you misused the recursion; you only replaced the loop with a recursive call.

Here is a simple example, to change the loop to recursion:

for(int i = 0; i < 3; i++) {
    // do something
}

Can be replaced by

  i = 0; // global variable
           //so that it maintains the value during recursive function calls
    void func() {
        // do something
        if(i < 3)
            func();
        i++;
    }

But good recursion is using the same function to do something meaningful.

Here is the beloved implementation for Fibonacci numbers:

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

Note how we made the function calculate itself by calling itself, and let the terminating condition do the magic! So when n = 0 or 1 it will return to the immediate caller with these numbers as a seed to the calculations.

So fib(1) = 1 and fib(2) = 2... and as we return back in the recursion stack, fib is being calculated.

Note that computing as a top down approach is exponential, but a down up approach whilst remembering the calculated fib (dynamic programming) is O(n), and is much more efficient way.

MeetTitan · Accepted Answer · 2016-08-02 13:49:15Z

0

public static void printFIBO(int n) {
    System.out.println(n <=1 : n ? fib(n-1) + fib(n-2));
}

edited Aug 2, 2016 at 13:49

MeetTitan

3,5851 gold badge16 silver badges31 bronze badges

answered Mar 27, 2016 at 10:46

user5961012

3 Comments

MeetTitan Over a year ago

This doesn't compile. Sorry buddy :(

MeetTitan Over a year ago

printFIBO returns void, meaning that you shouldn't return something from it. Also System.out.print(String) writes the string to stdout, and also returns void, meaning--you guessed it--it doesn't return. So you can't return from your function that doesn't return, a value that doesn't exist. Very close, though! :)

Michael Parker Over a year ago

While this code may answer the question, providing additional context regarding how and/or why it solves the problem would improve the answer's long-term value.

Collectives™ on Stack Overflow

Recursive Fibonacci code

6 Answers 6

Comments

4 Comments

2 Comments

Comments

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Comments

4 Comments

2 Comments

Comments

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related