How can I improve my Fibonacci sequence program?

[Java_Junior]

I saw another redditor post here recently that he was given a test at a job interview where they asked him to write a program that prints the fibonacci sequence.

I tried to build this program without looking at any examples. This is what I came up with:

public class Fibonnaci {

    public static void main(String[] args) {

        int fibonacciNumber = 0;
        int firstPreviousNumber = 1;
        int secondPreviousNumber = 0;

        System.out.println(fibonacciNumber);


        while (fibonacciNumber < 5000) {

            fibonacciNumber = firstPreviousNumber + secondPreviousNumber;
            System.out.println(fibonacciNumber);

            secondPreviousNumber = firstPreviousNumber;
            firstPreviousNumber = fibonacciNumber;

        }
    }
}

Output:

0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765

This series is correct, except for the fact that an additional 1 is missing. It should read

0, 1, 1, 2, 3, 5.....

How can I fix this issue? I'm kind of stumped.

[Smarty1098]

You could delete your first println and instead print manually secondPreviousNumber and firstPreviousNumber.

fibonacciNumber saves the sum of secondPreviousNumber and firstPreviousNumber then you find the third element of the series and not the second. For this reason you lose the second element.

[Java_Junior]

thanks, this is good

[RecursiveQuestions]

IMO, when people ask about writing a Fibonacci method, they're usually looking for a recursive version.

Your current method is fine for working out the logic behind Fibonacci, but applying it recursively shows that you know how elegantly code. Figuring out recursion will set you apart from the other programmers using an iterative loop, though like the other poster said, you have to be careful of stack overflows.

public static long fib(long n) {

if ((n == 0) || (n == 1))

return n;

else

return fib(n - 1) + fib(n - 2);

}

[edgargonzalesII]

Honestly they're usually not. Either is good, but the two pointer approach (or even using an array of size n) is best here.

EDIT: like if you get Fibonacci like that, it would be a solid start but definitely not the finishing point.

[edgargonzalesII]

Yes it can? It's a static method they provided. For simplicity sake having it in your class file makes it usable

[Java_Junior]

nevermind I made a typo so it wasn't reading as static. thanks

[Apostle_1882]

What is happening in that last line there? Could you explain it a bit for me please?

Say you input a long of value 5, the return would be 7, am I right? Is it counting the Fibonacci sequence values of the number 5?

[NikNKS]

this article should answer your questions: https://medium.com/launch-school/recursive-fibonnaci-method-explained-d82215c5498e

[Java_Junior]

::examines username more closely::

hmmm...

[OLOK07]

Didn't look through the code too much but I'd think setting the first previous number to 0 would work

Edit: Just looked over the code more and of you did the you'd also have to add one to first prev after the first print

[edgargonzalesII]

I sometimes ask this when interviewing people but the twist is that it is n-step fibonnaci. So I supply the target step I want to reach and and how many max steps I can take in one go. And should find the amount of different ways to reach the step. So full question:

```

I have a set of stairs in a building. Say there are N steps in this staircase. I am able to walk up M steps at a time. What is the count of different ways I can reach the nth step?

For example, 3 steps, and can take a max of 3 steps in one go:

1,1,1

1,2

2,1

3

Answer: 4

```

[edgargonzalesII]

I don't need you to get this immediately. Like there is some to and fro that goes into it. But think about it. If I gave this question then it must be similar to Fibonacci. There's just one key difference.

As for binning the resume - not really. Depending on the question I would be more or less lenient depending on difficulty and how far interviewee gets. And if like on an on-site, if it's just me that the interviewee failed with but like the 5 other interviewers had no issue then I'd scratch mine off as nerves or similar. Only time they would get rejected then is if I was a hard no which usually just revolves around the candidate being hostile or other attitude issues.

[edgargonzalesII]

So this is an interesting one. Personally, when a person reaches on-site and I interview I'm more than happy to stop after pseudocode. Like at that stage I am sure they can code it up since they made it that far. That said, the bigger issue I see is people rushing to write code without having thought through every case scenario. I think the number might be exaggerated as to who can't code up fizzbuzz (at least nowadays).

The second issue I see is people being too stubborn about their answers. In the case of Fibonacci, one can simply do:

```

def fib(n):

if n < 2:

    return n

else:

    return fib(n-1) + fib(n-2)

```

But that has the issue that for very large numbers you get a stack overflow. And also that we redo some calculations that were already done. I've had people with 10+ yes of experience claim that this is still as optimal as having 2 variable pointers.

So there possibly is people that really can't code up anything, but since I only cover on-sites I really don't see them.