For loop effecting recursion variables

Viewed 71

I am trying to use recursion to create a function that can get any term from any sequence within pascals triangle. Basically using the natural numbers as the adding sequence for the first set, and then using each previous set as the adding sequence, always starting at 1. Simplex Numbers

I am currently learning JavaScript and am doing what I already know works in Python to test some basic principles in JavaScript. However the for loop always seems to skip some numbers. What I belive is happening is that when the function calls itself, and runs the for loop again it is affecting the variable I from the function one level higher causing it to jump over a number in the sequence. I have no idea how to avoid this becuase JavaScript lets the variable be used in functions in the same scope, which makes sence, but I don't know how to avoid that.

 var simplex = function(s,t){
  if (s == 1){
    return t
  } else{
    var n=1;
    for (i = 1; i<t; i++){
      n += simplex(s-1,t+1);
    }
    return n
  }

}

console.log(simplex(3,3))
3 Answers

If you don't declare a scope for i it ends up persisting across recursive calls. You should always declare these in as narrow a scope as necessary.

Here's a cleaned up version:

function simplex(s,t){
  if (s == 1){
    return t
  }
  
  let n = 1;
  
  for (let i = 1; i < t; i++){
    n += simplex(s-1, t+1);
  }
  
  return n;
}

console.log(simplex(3,3));

Since it's 2020 and let and const are widely supported it's recommended to use those in preference to the old var style which has different scoping considerations. let is much more narrow and matches expectations a lot more closely.

As a matter of habit you should strive towards writing loops in the form of:

for (let i = 0; ...)

Where the let is clearly present. This makes it clear that the iteration variable only has relevance in that for loop.

In javascript, variables have function scope.

As @Barmar says in the comments, the problem is in this line:

for (i = 1; i<t; i++)

If you typed

for(var i = 1; i<t; i++)

then you are declaring a new variable i inside this function and your problem is solved.

When you type something like this in javascript:

i = 1;

If i has not been declared, you will implicitly be creating a variable i and assigning it to the global window object.

You can demonstrate it with this simple code:

i = 7;
console.log(`window.i = ${window.i}`);

Others have pointed out the fairly simple issue with an undeclared variable.

But even after that fix, there are still three logical errors. You're not using the loop variable i inside the loop. While there are times where this is ok, it's not here. You need it as an argument to simplex. Second, your loop bounds stop short. You want the t entries of the previous column, but you stop with the t - 1st one by testing i < t. Finally, you start your accumulation (n) with 1. Sums should start accumulating with 0. Fixing these, we have a working function that looks like this:

const simplex = function(s, t) {
  if (s == 1) {
    return t
  } else {
    var n = 0;
    for (let i = 1; i <= t; i++){
      n += simplex(s - 1, i)
    }
    return n
  }
}

Adding some logging statements to show the flow, we can get this:

const simplex = function (s, t, d = 0) {
  console.log('|   '.repeat(d) + `simplex (${s}, ${t})`)
  if (s == 1) {
    console.log('|   '.repeat(d) + `\`+-> ${t}`)
    return t
  } else {
    var n = 0;
    for (let i = 1; i <= t; i++){
      n += simplex (s - 1, i, d + 1)
    }
    console.log('|   '.repeat(d) + `\`+-> ${n}`)
    return n
  }

}

simplex (3, 3) //=> 10
.as-console-wrapper {max-height: 100% !important; top: 0}

simplex (3, 3)
|   simplex (2, 1)
|   |   simplex (1, 1)
|   |   `+-> 1
|   `+-> 1
|   simplex (2, 2)
|   |   simplex (1, 1)
|   |   `+-> 1
|   |   simplex (1, 2)
|   |   `+-> 2
|   `+-> 3
|   simplex (2, 3)
|   |   simplex (1, 1)
|   |   `+-> 1
|   |   simplex (1, 2)
|   |   `+-> 2
|   |   simplex (1, 3)
|   |   `+-> 3
|   `+-> 6
`+-> 10

But I believe this function can be simplified in many ways. There are simple things, like moving the else block out to the root, and using an arrow function in place of your function expression. Much more important to my mind is to use a helper function like sum to total up a number of values rather than including that logic in this function. By also including countTo, which simply returns the first n counting numbers, we can use map, making the code much more declarative. So I would probably prefer a version like this:

const countTo = (n) => n < 1 ? [] : [...countTo (n - 1), n]
const sum = (xs) => xs .reduce ((a, b) => a + b, 0)

const simplex = (s) => (t) =>
  s == 1
    ? t
    : sum (countTo (t) .map (simplex (s - 1)))

console .log (simplex (3) (3))

This version also makes one change to the API. Instead of a function that takes the simplex number and the term and returns the value, this one takes the simplex number and returns a function that takes the term and returns the value. It means calling it like simplex (s) (t) rather than simplex (s, t). It's not much harder to do this, and it has many benefits. But it would be easy enough to convert it to the other format, adding only a very minor complexity to the implmentation.


Update

I forgot to mention my first approach, which was to see the simplex number as an indexing directly into Pascal's Triangle. Pascal's triangle contains the binomial coefficients, which can be calculated with the simple recursion choose (n, k) = choose (n, k - 1) + choose (n - 1, k - 1), with some simple base cases.

Using that, simplex (s, t) is just choose (s + t - 1, t). It might look like this:

const choose = (n, k) =>
  k == 0
    ? 1
  : n == 0
    ? 0
  : choose (n - 1, k) + choose (n - 1, k - 1)

// Ex: choose (7, 3) //=> 35

console .log ('Pascal Triangle:\n');
console .log (
  Array .from (
    {length: 9}, 
    (_, n) => Array .from ({length: n + 1}, (_, r) => choose (n, r))
  ).map (
    r => r .map (n => `${n}`.padStart(2, ' ')) .join (' ')
  ) .join ('\n') + '\n ...'
)

const simplex = (s, t) => 
  choose (s + t - 1, t)
  
console.log ('simplex (3, 3): ', simplex (3, 3))
.as-console-wrapper {max-height: 100% !important; top: 0}

Related