Determine Fibonacci Number from User Input using Recursion

Question

From my homework, I need to have the user enter a number in numeric form, and convert it to the simultaneous fibonacci number from the sequence, while using recursion.

My question is how can I make the sequence through an array but not store it, so the array can be the size of the number the user entered... Here's some starting code I have:

import java.util.Scanner;

public class ReverseUserInput1 {
    //a recursive method to reverse the order of user input
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);   
        ReverseUserInput1 reverseIt = new ReverseUserInput1();    //creates new object

        System.out.print("Program to convert a number to a fibonacci number,");
        System.out.print("  - press Enter after each number.  ");
        System.out.println("- type \'0 or 1\' to finish the program.");
        System.out.print(" --Enter a number: ");
        int aNum = in.nextInt();

        reverseIt.reverseInput(aNum); //invokes reverseInput() method
    }

    public static int reverseInput() {
        if(aNum == 0) {
            return aNum;
        }
        else if(aNum == 1) {
            return aNum;
        }     
        else {
            reverseInput();
        }

        System.out.println(aNum);       
    }
}

I think what you are supposed to do for your homework is create a recursive method int fibonacci(int n) which returns the nth number in the Fibonacci sequence. You have to read the argument n from the user input. Please have a look at what the Fibonacci sequence is, look at notes on recursion and give it a go. Currently, your reverseInput() does not work. Identify that any Fibonacci number is the sum of the previous 2, except the first 2 numbers which are 1. Or just Google 'recursive fibonacci', but since it's your homework that's a bit cheap. — Daniël Knippers
– Daniël Knippers, Commented Feb 25, 2014 at 23:27
A quick Google search will return largely enough hits -- including questions on this very own site — fge
– fge, Commented Feb 25, 2014 at 23:33

Elliott Frisch · Accepted Answer · 2014-02-26 19:50:46Z

Here is one method, note that this also includes the negafibonacci sequence;

private static Map<Integer, BigInteger> fibCache = 
    new HashMap<Integer, BigInteger>();

public static BigInteger fib(int n) {
    // Uses the following identities, fib(0) = 0, fib(1) = 1 and fib(2) = 1
    // All other values are calculated through recursion.
    if (n > 0) {
        // fib(1) and fib(2)
        if (n == 1 || n == 2) {
            return BigInteger.ONE;
        }
        synchronized (fibCache) {
            if (fibCache.containsKey(n)) {
                return fibCache.get(n);
            }
            BigInteger ret = fib(n - 2).add(fib(n - 1));
            fibCache.put(n, ret);
            return ret;
        }
    } else if (n == 0) {
        // fib(0)
        return BigInteger.ZERO;
    }
    if (n % 2 == 0) {
        return fib(-n).multiply(BigInteger.ZERO.subtract(BigInteger.ONE));
    }
    return fib(-n);
}

public static void main(String[] args) throws Exception {
    for (int x = -8; x <= 8; x++) {
        System.out.println(fib(x));
    }
}

Outputs

Daniël Knippers · Accepted Answer · 2014-02-26 20:06:17Z

0

I was not going to post the actual algorithm (see my comment to his question earlier), but then I saw an unnecessarily complex version being posted. In contrast, I'll post the concise implementation. Note this one returns the sequence starting with 1,1,2. Another variant starts with 0,1,1,2 but is otherwise equivalent. The function assumes an input value of 1 or higher.

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

That's all.

answered Feb 26, 2014 at 20:06

Daniël Knippers

3,0551 gold badge14 silver badges17 bronze badges

Collectives™ on Stack Overflow

Determine Fibonacci Number from User Input using Recursion

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related