Fibonacci with a Twist - JavaScript

Question

I was asked this question for a JavaScript interview.

Implement fibonacci series to list the sequence up n numbers (n not included) where recursion happens only for even numbers. for example

fib(10) -> fib(8) + fib (6)
fib(8) -> fib(6) + fib(4)
fib(6)  -> fib(4) +fib(2)
fib(4) -> fib(2)

I am not sure how to go about this.

Answer 1

Consideration

fib( 4) = fib( 2)           =  1 * fib(2)
fib( 6) = fib( 4) + fib( 2) =  2 * fib(2)
fib( 8) = fib( 6) + fib( 4) =  3 * fib(2)
fib(10) = fib( 8) + fib( 6) =  5 * fib(2)
fib(12) = fib(10) + fib( 8) =  8 * fib(2)
fib(14) = fib(12) + fib(10) = 13 * fib(2)
                               ^
                               this is fibonacci

In code we get this - a nice little recursion (valid for all even n >= 0):

var i;

function fib(n) {
    switch (true) {
        case n === 0:
            return 0;
        case n === 2:
            return 1;
        default:
            return fib(n - 2) + fib(n - 4);
    }
}

function writeFib(n) {
    document.write('fib(' + n + ') = ' + fib(n) + ' * fib(2)<br>');
}

for (i = 0; i <= 20; i += 2) {
    writeFib(i);
}

If you want a result like fib(10) -> fib(8) + fib(6), then this will do it (no recursion):

var i;

function fib(n) {
    switch (true) {
        case n === 0:
            return '0';
        case n === 2:
            return 'fib(2)';
        default:
            return 'fib(' + (n - 2) + ') + fib(' + (n - 4) + ')';
    }
}

function writeFib(n) {
    document.write('fib(' + n + ') -&gt; ' + fib(n) + '<br>');
}

for (i = 0; i <= 20; i += 2) {
    writeFib(i);
}

Answer 2

This definitely needs more clarification. (Interviewer should probably have been more clearer).

But from what I understand...

So the series has to start somewhere and I'm assuming it starts at fib(2) = 1. And going with the "code" part given by the interviewer.

This could be as simple as:

• fib(2) = 1
• fib(4) = 1
• fib(6) = 2
• ...

i.e. fib(n) = fib_orig(n/2)