Christopher Nash Christopher Nash - 4 months ago 16
Javascript Question

Stacks and recursive functions

I hope this is not a repeated question-- though I couldn't find much help on this.

I am practicing recursive functions (I'm a newbie), and I'm trying to multiply each number in an array. Sort of like a factorial. I have this code, but it is only returning

undefined
as a result.

Here is the code:

var stack = [];

function countDown(int) {
stack.push(int);
if (int === 1) {
return 1;
}
return countDown(int - 1);
}

function multiplyEach() {
// Remove the last value of the stack
// and assign it to the variable int
int = stack.pop();
x = stack.length;
// Base case
if ( x === 0 ) {
return;
}
// Recursive case
else {
stack[int - 1] = int * stack[x - 1];
return multiplyEach(int);
}
}

// Call the function countDown(7)
countDown(7);
// And then print out the value returned by multiplyEach()
console.log(multiplyEach());


Thank you so much for any insight.

Cheers!

Answer

The first thing to address is that your multiplyEach() function should have a parameter named int, from the looks of it. The approach you're using might be better suited to a different technique, but we'll get to that.

Next, in multiplyEach(), there are two possible paths:

  1. The stack still has elements, in which case we multiply the new top value on the stack by the old one and move on to another run of multiplyEach.

  2. The stack is empty, and we just return.

The problem here is that we aren't actually returning the final stack value, or leaving it on there to access later. We've effectively lost it, so what is the function outputting?

In many languages, we would have defined a return type for this function, either void for no value, or int for returning the multiplied value. However, in Javascript, there is no such thing as a function that doesn't return a value; "nothing" in JS is represented as undefined. When you return multiplyEach(), you're pushing another call of it onto the call stack, and waiting for an actual return value... which ends up being return;, which JS interprets as return undefined;. Again, in most languages, there would be some form of error, but not in JS! Let's look at two possible implementations:

  1. The custom stack you use:

    // your stack is fine, so we'll skip to the meat
    function multiplyEach() {
        var int = stack.pop(), x = stack.length;
        stack[x - 1] *= int;
        if(x < 2) // to multiply, we need at least two numbers left
            return;
        multiplyEach();
    }
    
    //...
    multiplyEach();
    console.log(stack[0]);
    
  2. With a parameter, and using a list:

    function multiplyEach(index) {
        var int = list[index];
        if(index == 0)
            return int;
        return int * multiplyEach(index - 1);
    }
    
    //...
    console.log(multiplyEach(list.length - 1));
    

They're both different ways of implementing this recursively; all recursion inherently requires is for a function to call itself. Another possibility would have been having a parameter store the total, instead of multiplying the return values like in option 2; that's called tail recursion.

EDIT: noticed the base case for option 1 was in the wrong place, so I moved it. It should work now.