Practical Task - Fibonacci sequence

Task : Write a function that calculates n-th element of the Fibonacci sequence. First two numbers are 1, every other is the sum of two preceding ones. https://en.wikipedia.org/wiki/Fibonacci_number

1. Example solutions:

Iterative algorithm:

    public static int getFibonacciNumber(int n) {
        int previous1 = 1, previous2 = 0;
        int current = 1;
        for (int i = 0; i < n; i++) {
            current = previous1 + previous2;
            previous2 = previous1;
            previous1 = current;
        }

        return current;
    }

Recursive algorithm:

    public static int getFibonacciNumberRec(int n) {
        if (n < 2) return 1;
        return getFibonacciNumberRec(n - 1) + getFibonacciNumberRec(n - 2);
    }

2. Advantages and disadvantages of each approach.

The recursive approach looks definitely nicer. Such code is more functional and it's more similar to natural language. The issue is that even though it is much faster for smaller numbers (uses fewer variables, fewer operations) it quickly gets more problematic. We can easily notice that "getFibonacciNumberRec" function is going to be called more than one with the same input. for instance, to calculate 5th number we need to know what's the 4th and 3rd element, to calculate 4th element we have to calculate 3rd and 2nd element. So already 3rd element appears 2 times and will be calculated separately. This can be easy visualized by this diagram (for 4th element)

                    f(1)
              f(2)<  +
        f(3)<  +    f(0)
       /      f(1)
      /
f(4) <   +
      \
       \      f(1)
        f(2)<  +
              f(0)

every next element would double the size of this tree. So the number of operation is proportional to 2ⁿ which mean that this solution has the exponential runtime ( O(2ⁿ) ). More of that, even though we're not declaring more variables, every call stacks in the memory which means the solution require space which is proportional to 2ⁿ.

The iterative solution takes number of steps equal to n, which means that the number of operations is proportional to n - linear solution ( O(n) ). Also it does not declare more variables during the work, which means it needs a constant amount of memory.

This may lead us to opinion that we should never use the recursive approach in this case. But it's not completely true. We can improve the second approach by implementing a technique called memoization (https://en.wikipedia.org/wiki/Memoization). In the nutshell - it's about storing already calculated values. This will require additional space but will improve our solution to have linear computational complexity ( O(n) ).

    private static Map<Integer, Integer> fibonacciNumbers = new HashMap<>();
    
    public static int getFibonacciNumberRec2(int n) {
        return fibonacciNumbers.computeIfAbsent(n,  i ->
                (i < 2) ? 1 : getFibonacciNumberRec2(i - 1) + getFibonacciNumberRec2(i - 2));
    }

3. Return type.

One of the problems we might have with proposed solutions is the maximum value for integer in Java. Unfortunately Fibonacci numbers get big very soon, which means we can calculate only up to 45th element. Next value is 2971215073 and maximum value for integer is 2147483647. To calculate bigger values we should use long (up to 93rd element - 7540113804746346429 ) or BigInteger which theoretically don't have any maximum value and should be able to return any result.

4. Few tips

• you might have to write code with IDE, online platform or even a whiteboard. Practise all! Use both sheet of paper and online testing platforms like http://www.spoj.com/ or https://www.codility.com/ or any other.
• take care of naming conventions. No one probably will care if you forget a semicolon on the whiteboard but "getFibonacciNumber(int n)" looks much better than "fun(int a)" or "foo(int bar)"
• think about clean code. Practical tasks are to check what kind of code do you normally write. It should be readable for the whole team, not only you.
• don't be afraid to think all loud. It's much better when you get the solution slower but you are able to verbalize your thoughts than writing the program instantly but without any explanation.
• think before writing! Ask questions if needed. Sometimes you may finish in a dead end if you choose the wrong path.
• think about corner cases. Check how your program will behave with different values like 0, null, MAX_INTEGER, empty string etc.

Any more? ;)

used examples are available here:
https://ideone.com/Ovt4l7