Solve Fibonacci sequence recursively without prior digits

Question

Is there a way to print the Fibonacci sequence up to the nth digit without any information before hand? Here's one of my methods to do so, although it us using prior information.

int p;
int n = 0;
String fib = "0, 1";

public printFib () {
    String fibSequence = fibPrint(0, 1, x); //x denotes xth fib number
    System.out.println(fibSequence);
}

private String logicFib (int a, int b, int c) {
    if (n == c-2) {
        return fib;
    } else {
        n++;
        p = a + b;
        fib = fib + ", " + p;
        logicFib(b, p, c);
    }
}

The problem here is that I'm printing digits 3, 4, 5, ... n on top of digits 1, 2, when I would like to print them all without first declaring the first two digits. My method's logic only works if the first two digits are already known, when I'd like to forgo this.

Answer 1

I think the standard solution for Fibonacci would look like the following:

public class Fibonacci {

    public long fibo(long n){   
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;
        else
            return fibo(n-1) + fibo(n-2);
    }

    public static void main(String...args){

        int n = 20;
        Fibonacci f = new Fibonacci();
        for(int i = 0; i < n; i++){
            System.out.println(f.fibo(i));
        }
    }
}

In a recursive method you always need a break condition. In the case of this fibonacci method this would be the 0th and 1st fibonacci number as you can recognize above. There is no other way to calculate the fibonacci number recursively. You simply need the break condition.

If you don't need the recursive character of your method you can calculate the number via the Binet's formula. For further information about this one click here.

EDIT:

I change my method. It's now counting up till the nth Fibonacci number.

Answer 2

Well you have know limit, because you have to know how many numbers you want to print.

public class Fibonacci {
    public int limit = 10;
    public int left=0, right=1;
    public int next;
    public void countNextFibo(int limit) {
        if(this.limit==0) {
            return;
        }
        else {
            System.out.print(left+", ");
            next = left+right;
            left = right;
            right = next;            
            --this.limit;
            countNextFibo(this.limit);
        }
    }

    public static void main(String args[]) {
        Fibonacci f = new Fibonacci();
        f.countNextFibo(10);
    }
}

Answer 3

This solution uses the Iterator interface. When run it calculates all fibonacci numbers in the long range. The accepted answer is doubly exponential time since it's O(n^2) for each call. On my computer changing n to 93 to do the same as my program it will use several hours to compute the same list this code does in 0.09 seconds.

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.lang.IllegalArgumentException;

public class Fibonacci implements Iterable<Long>
{
    final int FIB_MAX_LONG_INDEX = 92; // highest index producing correct long 
    int fromIndex = 0;
    int toIndex = FIB_MAX_LONG_INDEX;

    public Fibonacci(int fromIndex, int toIndex)
    {
        if( fromIndex > toIndex )
            throw new IllegalArgumentException("toIndex must be same or greater than fromIndex");

        if( toIndex > FIB_MAX_LONG_INDEX )
            throw new IllegalArgumentException("toIndex must be lowe or equal to 92 to not overflow long");

        this.fromIndex = fromIndex;
        this.toIndex = toIndex;
    }

    public Fibonacci(){}

    private class FibonacciIterator implements Iterator<Long>
    {
        private long cur = 0, next = 1;
        private int index=0;

        public boolean hasNext()
        {
            return index <= toIndex;
        }

        public Long next()
        {
            if ( index > toIndex )
                throw new NoSuchElementException();

            long tmpCur;
            do {
                tmpCur = cur;
                cur = next;
                next +=tmpCur;
                index++;
            } while ( index <= fromIndex );

            return tmpCur;
        }

        public void remove()
        {
            throw new UnsupportedOperationException();
        }
    }

    public Iterator<Long> iterator()
    {
        return new FibonacciIterator();
    }

    public static void main (String[] args)
    {
        Fibonacci fib = new Fibonacci();
        for (long i : fib)
        {
            System.out.print( i + " ");
        }
        System.out.println();
    }
}

The output when run (I've added some linefeeds):

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597
2584 4181 6765 10946 17711 28657 46368 75025 121393
196418 317811 514229 832040 1346269 2178309 3524578
5702887 9227465 14930352 24157817 39088169 63245986
102334155 165580141 267914296 433494437 701408733
1134903170 1836311903 2971215073 4807526976 7778742049
12586269025 20365011074 32951280099 53316291173 
86267571272 139583862445 225851433717 365435296162 
591286729879 956722026041 1548008755920 2504730781961
4052739537881 6557470319842 10610209857723 
17167680177565 27777890035288 44945570212853 
72723460248141 117669030460994 190392490709135 
308061521170129 498454011879264 806515533049393 
1304969544928657 2111485077978050 3416454622906707 
5527939700884757 8944394323791464 14472334024676221 
23416728348467685 37889062373143906 61305790721611591
99194853094755497 160500643816367088 
259695496911122585 420196140727489673 
679891637638612258 1100087778366101931 
1779979416004714189 2880067194370816120 
4660046610375530309 7540113804746346429 

But as you see you can make just about any index range. the following loops over 30 to 39 and ends up printing 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986

Fibonacci fib = new Fibonacci(30, 39);
for( long i : fib) {
    System.out.print(i + " "); 
}