It’s 6 PM. I’m tired and after a long day at work. I’ve arrived at the interview site and met the team leader whom I will be working with. we start with the basic “Tell me about yourself questions”, and go straight to the JavaScript coding test.

I’ve been handed a piece of paper, 30 minutes to solve the test, Go!

Most of the questions were pretty straight forward, explain the event loop, a few programs that I need to evaluate their results, and then I saw the recursion question.

Question: Write a recursive function that prints the Fibonacci Sequence in ascending order. The function receives as parameters the last and second last numbers of the sequence. Example: printFibonacci(55,34) -> 1 1 2 3 5 8 13 21 34 55

If you don’t already know the answer, take a moment to think about the solution.

At first I thought “It’s easy, I’ve got this!”, but then I started to struggle, I’ve already spent most of my time solving the other questions, I had around five minutes left to solve the question, but I couldn’t come up with a solution. All I could think of was the basic Fibonacci recursion that prints in descending order. I couldn’t figure out how to print the results in ascending order, and I ended up failing miserably.

Course by Sagi Liba,
Author of this blog

Fibonacci Descending Order

// The code will print: 55 34 21 13 8 5 3 2 1

function printFibonacci(last, secondLast) {
  if (last == 1 && secondLast == 0) {
    return;
  }
  console.log(last);
  // Moving to the next fibonacci numbers
  return printFibonacci(secondLast, last - secondLast);
}
printFibonacci(55, 34);

In the above solution I’ve made two mistakes:

1. Fibonacci sequence for this question starts with the values: 1 1 … My stopping condition was correct, but it would only print “1″ one time.

2. I’ve used “return”, therefore any code written after that return statement will not be executed. This was the error that prevented me from solving the question.

After the time was up, I sat down with the team leader to go over the test. Apparently this question was the most important one for him, because it’s meant to show him my thought process, therefore I believe this was the question that cost me the job offer. I haven’t encountered such a recursion since my first year at college studying computer science.

We started discussing options to solve the question, and I’m trying to show him my thought process, but still I was not able to arrive at a solution.

Lets go over the solution together so you won’t fail at this question like I did.

Solution

// The code will print: 1 1 2 3 5 8 13 21 34 55

function printFibonacci(last, secondLast) {
  // The code above the recursive function call will be in descending order.
  if (last == 1 && secondLast == 0) {
    console.log(1);
    return;
  }

  // Recursive function call, Moving to the next fibonacci numbers
  printFibonacci(secondLast, last - secondLast);

  // The code below the recursive function call will be in ascending order.
  console.log(last);
}
printFibonacci(55, 34);

Any code above the printFibonacci recursive function call will run in descending order.

Any code below printFibonacci recursive function call will run in ascending order.

Lets look at the call stack to truly understand what happens:

Every time we reach the recursive function call (PrintFibonacci) we go one level deeper inside the recursion. When we reach the last function call in the recursion we start running each of the calls we’ve put in our call stack.

We start from the last call (1,0), as seen in the image above, therefore printing the first Fibonacci value of the sequence (1) by hitting the stopping condition. Next, we go to the second function call (1,1) and print the second value of the sequence and so forth.

After grasping the idea that the order in which I put the recursive call shifts the order of code execution, I finally understood how it truly works.

I hope this will help you with your next interview.