Home > Software engineering >  Recursion and Arrays. What does 'return' actually do here?
Recursion and Arrays. What does 'return' actually do here?

Time:01-26

I'm currently working through freeCodeCamp's JS course.

One of the last problems asks you to create a recursive function that only accepts one argument n and creates an array that counts down from n to 1.

I was able to solve the problem using this code (SPOILERS IF YOU ARE ALSO WORKING ON THIS PROBLEM):

// Only change code below this line
function countdown(n) {
  if (n < 1) {
    return [];
  } else {
    const countArray = countdown(n - 1);
    countArray.unshift(n);
    return countArray;
  }
}
// Only change code above this line

// my test
console.log(countdown(1))

I mostly arrived at this answer by copying syntax in the provided example. I plugged my answer into Python Tutor's code visualizer here. I will be referencing the steps in this visualizer.

Question about step 3: I notice it says countArray (block 1) is undefined. I assume this is because the function is hanging onto n and will go back and populate the array once the base statement creates it? Does this mean the defining of the array is delayed until the base case is reached?

Question on step 6: I see that my code worked as intended and now that n is 0, the base case is activated and the function returns an empty array. How does the code know that I want to populate this empty array with countArray? What ties the two together.

Question on step 7: If you can only answer one of my questions, I would like it to be this one.: Why does the function continue at all after the base case was reached (when n = 0)? From my flawed understanding return ends the function immediately. By this logic, my code shouldn't do what is intended. It would always count n down, and then regardless return an empty array.

Thank you for reading my question. If my thoughts are not detailed clearly enough here, please let me know how I can clarify.

CodePudding user response:

Recursive function calls are stacked on top of the previous call.
So taking an example of countdown(2),

  1. n > 0, i.e run else part which saves the value returned by countdown(1).
  2. So now we go to countdown(1), which sends us to countdown(0).
  3. Now, countdown(0) returns us an empty array.
  4. From here, we run the left over part of countdown(1), i.e countArray = [] , which we got from countdown(0)
  5. unshift means push value at start of array. So now our array is countArray=[1]
  6. We return this value to countdown(2) (the first line). And now our countArray = [1] is in our initial function call.
  7. Then we run the left over part again: countArray.unshift(2) -> [2, 1]
  8. And finally we return it to whatever called it.
// Call Stack: 
countdown(2) -> countdown(1) -> countdown(0)

// return Stack: 
[2, 1] <- [1] <- []

Bonus: below is a one liner for the required function

const countdown = (n) => n ? [n, ...countdown(n - 1)] : []
console.log(countdown(5))

CodePudding user response:

No array is created until you reach the base case.

When you call a function, a new context with its own local variables (called a stack frame) is created. Your visualizer shows these on the right ("Frames").

Notice how a new frame appears going from step 3 to 4. Then, when the base case returns going from step 6 to 7, the frame disappears again. The execution picks up where it left off before evaluating the base case, with the only difference being that the value for countArray is known.

return only finishes the current context, returning the intermediate result to its parent context. Basically, each level of recursion is independent here.

  • Related