Recursion Viewer (dmytrobaida.github.io)

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;
    }

    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;
    }

This is really cool. Does anybody know one that do the same for Python?

Adding animation would make it more engaging.

This is good, but a tree structure never works for me. It has no temporal component. Anything similar available?

I am developing an online IDE capable of visualizing a program's call tree. Within this IDE, users can select a node in the call tree to observe detailed information, including function arguments, return values, local variables, and intermediate expressions. Additionally, the IDE features a time-travel engine that displays the values of mutable objects at the specific moment when a particular function and statement were executed.

You can try it online here: https://app.leporello.tech/?example=fibonacci

i would've wanted to see the simple ackermann function visualized, but the recursion isn't allowed to be deep enough!

    function ack(x: number, y: number): number {
      if (x === 0) return y + 1;
      if (y === 0) return ack(x-1, 1);
    
      return ack(x - 1, ack(x, y-1))
    }

Oo! I did something like this for logging the js function call stack. It was fun on recursive examples.

https://github.com/ando818/Svelte-Logger

I took the Ackermann function [1] from Rosetta Code [2]:

    function ack(m: number, n: number): number {
      return m === 0 ? n + 1 : ack(m - 1, n === 0  ? 1 : ack(m, n - 1));
    }

I tried `ack(m = 2, n = 2)` but the recursion depth prevented (3, 2) or (2, 3).

[1] https://en.wikipedia.org/wiki/Ackermann_function

[2] https://rosettacode.org/wiki/Ackermann_function#JavaScript

When I was in school learning about recursion for the first time, I only truly 'got' it when I opened up Excel and drew it out like this:

  fib(5) n=5 ----------------
  | n=5
  |-- fib(5-1=4) ------------
  |-- | n=4
  |-- | -- fib(4-1=3) -------
  |-- | -- | n=3
  |-- | -- | ...
  |-- | -- end of fib(3) ----
  |-- | here n is still 4
  |-- end of fib(4)
  | here n is still 5
  |-- fib(5-2=3) ------------
  |-- | n=3
  |-- | ...
  |-- end of fib(3)
  | here n is still 5
  end of fib(5)

with different colours for each invocation. The point I'd been missing/not taught very well is that each invocation has its own values for the arguments, and once that invocation returns, the previous invocation still has whatever values it used to have for the arguments. That was the key for me of 20 years ago, and the Excel visualisation was when the penny dropped.