4 ms·
Recursion Viewer
- shwestrick 3y agoEnjoyed 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 3y agoThanks 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; }
- iamcreasy 3y agoThis is really cool. Does anybody know one that do the same for Python?
- friendlynokill 3y agoPython Tutor lets you step through the execution of a function frame by frame: https://pythontutor.com/cp/composingprograms.html https://pythontutor.com/cp/composingprograms.html
- portpecos 3y agoAdding animation would make it more engaging.
- nayuki 3y agoIf you want to step through function execution, try https://pythontutor.com/visualize.html#mode=edit https://pythontutor.com/visualize.html#mode=edit
- sidcool 3y agoThis is good, but a tree structure never works for me. It has no temporal component. Anything similar available?
- andoando 3y agoIt’d be nice if it was animated but if it helps the order for the time in the tree should be: Higher nodes all occur before any of their lower nodes. Within the same depth, lefter nodes occur before righter nodes. So you can kinda visualize it if you read it bottem left to top right
- dmitry-vsl 3y agoI 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 https://app.leporello.tech/?example=fibonacci
- chii 3y agoi 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)) }
- andoando 3y agoOo! I did something like this for logging the js function call stack. It was fun on recursive examples. https://github.com/ando818/Svelte-Logger https://github.com/ando818/Svelte-Logger
- bArray 3y agoI 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 https://en.wikipedia.org/wiki/Ackermann_function [2] https://rosettacode.org/wiki/Ackermann_function#JavaScript https://rosettacode.org/wiki/Ackermann_function#JavaScript
- llimos 3y agoWhen 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.
- deleted 3y ago[deleted]
- supriyo-biswas 3y agoThis is why I believe the concept of the stack frame should also be introduced when teaching recursion. Otherwise, you get questions from students like, "how can you call the same function from within" and "wouldn't the value of n be overwritten when I call it again?"
- giovannibonetti 3y agoLisp has a trace command [1] that does exactly that. [1] https://lispcookbook.github.io/cl-cookbook/debugging.html#trace https://lispcookbook.github.io/cl-cookbook/debugging.html#tr...