CODEWITHSUNDEEP
javascriptrecursion
Sam
Sam

Reputation: 35

Another Recursive JavaScript function

Can someone visually explain what's going on here please.

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 int;
    }
    // Recursive case
    else {
        stack[x - 1] = int * stack[x - 1];
        return multiplyEach();
    }
}

// Call the function

 countDown(7);

// And then print out the value returned by multiplyEach() 

console.log(multiplyEach());

I sorta understand that's it's creating a stack and them multiplying everything together but I can't visualize it.

Then: 

Stack[x-1] is getting me

Upvotes: 0

Views: 388

Answers (3)

Abid
Abid

Reputation: 7227

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

this function is recursively adding the value of int to the stack variable, when the function finally returns the stack contains numbers from int to 1.

in more detail here is how this function is working

1- push int to the stack 2- if int is equal 1 return 3- otherwise call countDown(int-1)

the function will recursively call itself and keep pushing int to the stack untill int becomes 1. so the stack variable in the end contains the range [int, int-1, int-2, ... 1]. The following lines show the state of the stack array after each iteration of the function countDown

[int]
[int, int-1]
[int, int-1, int-2]
[int, int-1, int-2, int-3]
[int, int-1, int-2, int-3, int-4]
....
[int, int-1, int-2, int-3, int-4,......1]

This array is then used by the multipyEach function

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 int; 
  } 
// Recursive case 
  else { 
    stack[x - 1] = int * stack[x - 1];
    return multiplyEach(); 
  } 
}

This function removes the last element from the array and multiplies it the previous number in the array and stores it in that previous location ( stack[x - 1] = int * stack[x - 1];). Again this functions keeps calling itself until the size of array becomes 0. which will resulting number inside int will be factorial of it. below is the state of the array after each iteration of multiplyEach

[int, int-1, int-2, int-3, .... 4, 3, 2, 1]
[int, int-1, int-2, int-3, .... 4, 3, 2]
[int, int-1, int-2, int-3, .... 4, 6]
[int, int-1, int-2, int-3, .... 24]
.
.
[int!]

Upvotes: 1

Supr
Supr

Reputation: 19022

This is a two part algorithm.

First countDown(n) fills the array stack with values from n down to 1, so stack = [n, n-1, n-2, ..., 3, 2, 1]. The return value of countDown is never used and so the return statement can be ignored. The only thing that matters is that it fills the stack array as explained.

Second, multiplyEach repeatedly takes the last element of the stack, removes it, and multiplies it with the next last element in the array:

[n, n-1, n-2, ..., 6, 5, 4, 3, 2, 1]
[n, n-1, n-2, ..., 6, 5, 4, 3, 2]
[n, n-1, n-2, ..., 6, 5, 4, 6]
[n, n-1, n-2, ..., 6, 5, 24]
[n, n-1, n-2, ..., 6, 120]
...
[n!]

In other words, the algorithm calculates the factorial of the number n given to countDown.

Upvotes: 1

JKirchartz
JKirchartz

Reputation: 18022

int is being set to the value of the last array element and removing that from the array, x is being set to the post-pop length of the stack array, so stack[x-1] is getting the last element of the "new" array. if there's still stuff in the array it multiplies int and the new last element (previously the second to last) and stores it as the last element of the array. this then calls the process over again until the array is empty and all numbers are multiplied together.

Upvotes: 0

Related Questions