DEV Community

benboorstein
benboorstein

Posted on

freeCodeCamp Recursion Example Explained

/*
Note that the below recursion challenge can be found here:
https://www.freecodecamp.org/learn/javascript-algorithms-and-data-structures/basic-javascript/use-recursion-to-create-a-countdown.
But it's the *example* provided, not the challenge itself.
*/


function countup(n) {
    if (n < 1) { // the base case
        return []
    } else {
        const countArray = countup(n - 1) // remember that, on the way "down", each call is added to the stack
        countArray.push(n)
        // console.log(countArray) // just a helpful line
        return countArray
    }
}

console.log(countup(5)) // [1, 2, 3, 4, 5]


/*
fCC: "At first, this seems counterintuitive since the value of n decreases but the values in the final array are increasing.
This happens because the push happens last, after the recursive call has returned.
At the point where n is pushed into the array, countup(n - 1) has already been evaluated and returned [1, 2, ..., n - 1]."
*/


// The way "down":
    // countup(5 - 1) // added to stack first
    // countup(4 - 1) // added to stack second
    // countup(3 - 1) // added to stack third
    // countup(2 - 1) // added to stack fourth
    // countup(1 - 1) // added to stack fifth

// So the stack looks like this, top to bottom:
    // countup(1 - 1)
    // countup(2 - 1)
    // countup(3 - 1)
    // countup(4 - 1)
    // countup(5 - 1)

// The base case is reached:
    // countup(1 - 1) evaluates to countup(0)
    // ...which means n is 0
    // ...which means n < 1 is true
    // ...which means [] is returned to countup()
    // ...which means countArray = []

// The way "back up":
    // It is now that 'control' moves on to the 'countArray.push(n)' line
    // countArray = [1] // the 1 comes from the top of the stack (and then the 2 is at the top of the stack)
    // countArray = [1, 2] // the 2 comes from the top of the stack (and then the 3 is at the top of the stack)
    // countArray = [1, 2, 3] // the 3 comes from the top of the stack (and then the 4 is at the top of the stack)
    // countArray = [1, 2, 3, 4] // the 4 comes from the top of the stack (and then the 5 is at the top of the stack)
    // countArray = [1, 2, 3, 4, 5] // the 5 comes from the top of the stack (and then the stack is empty and countArray is returned)
Enter fullscreen mode Exit fullscreen mode

Top comments (0)