On: Recursion Viewer

[shwestrick]

Enjoyed playing with this!

N-queens search is another nice recursive example. E.g. call this with nqueens(0, 5, [])

    function nqueens(i:number, n:number, queens: number[][]) {
      if (i >= n) return 1;

      let count = 0;
      for (let j = 0; j < n; j++) {

        let is_threatened = false;
        for (let k = 0; k < queens.length; k++) {
          let x = queens[k][0];
          let y = queens[k][1];

          if (i == x || j == y || i - j == x - y || i + j == x + y) {
            is_threatened = true;
            break;
          }
        }

        if (is_threatened) continue;

        count += nqueens(i+1, n, Array(Array(i,j)).concat(queens))
      }

      return count;
    }

[tromp → shwestrick]

Thanks for showing the syntax to use! I computed the number of closed lambda terms of size 10 bits within 0 binders with nclosed(k=0, n=10) :

    function nclosed(k:number, n:number) {
      if (n < 2) return 0;
      let sum = nclosed(k+1,n-2); // Lambda
      for (let i = 2; i < n-1; i++) {
        sum += nclosed(k,i) * nclosed(k,n-2-i); // Application
      }
      if (n-2 < k) sum += 1;      // Variable
      return sum;
    }