Recursion, Iteration, & JavaScript: A love story

(presented at JS Heroes 2018: https://youtu.be/FmiQr4nfoPQ)

Recursion and iteration are two alternative paradigms for solving problems by breaking them down into smaller chunks; this talk is a deep dive into how these paradigms work, and how JS supports them both. There’s a fundamental tradeoff between the two: the stateful repetition of iteration is often more performant as it’s closer to the way our machines “think”, whereas many programmers find the self-referential abstraction of recursion easier to read & write. In JS prior to ES6, neither paradigm was especially easy to work with: iterative loops were laborious to read and write (not human-efficient), and recursion was limited by the fact that subsequent recursive calls to a function require additional frames added to the stack, potentially leading to stack overflow (not machine-efficient). Eventually, however, all three - recursion, iteration, and JS - were finally brought closer together. In this talk we’ll dive into the nature of the two paradigms, examine what an Iterable and a tail-recursive function are, and learn how Tail Call Optimization unites the two paradigms, allowing us to write code recursively and run it iteratively.

Transcript

1. Recursion, Iteration, & JS: A lo t @AnjanaVakil ❤ JSHeroes 2018
2. Bună! Mă c e ă @AnjanaVakil
3. location data platform for developers maps, search, navigation web, iOS, Android, Unity...
4. so m u t e I ♥ The Recurse Center recurse.com outreachy.org
5. I ♥ programming paradigms le ’s e d ! youtu.be/Pg3UeB-5FdA
6. t i s a f o star-crossed paradigms
7. Iteration v Recursion
8. Iteration Imperative Repetitive Stateful
9. Iteration Imperative Repetitive Stateful © Columbia Pictures 1993 - image via IMDb
10. Recursion Functional Self-referential Stateless © Warner Brothers 2010 - image via IMDb
11. Recursion Functional Self-referential Stateless © Warner Brothers 2010 - image via IMDb
12. Iteration v Recursion
13. t o r i m , bo l e dignity
14. bu h o t efficiency?
15. Jon n B o “Pro m g Ae h s e n ro k in n e t s” youtu.be/JjDsP5n2kSM - h/t Yo h
16. You might optimize for speed… You might optimize for space... But… there's a third thing you might want to optimize for, which is: years of your life required per program implementation. This is more important than those other things... or certainly equally important. Jon n B o “Pro m g Ae h s e n ro k in n e t s” youtu.be/JjDsP5n2kSM - h/t Yo h “ ”
17. Machine Efficiency Time Space Human Efficiency Writing Reading Maintenance v
18. in JavaScript we ur n
19. yu , I’m u n Shakespeare © 20th Century Fox 1996 - image via IMDb
20. bu h t ha happy ending
21. JS
22. Act I: Ite on, bu t i
23. > var simpleTree = makeTree(simpleTreeNode); We l ♥t e function simpleTreeNode(value) { return { value: value, left: undefined, right: undefined }; } function makeTree(nodeType) { var root = nodeType(0); root.left = nodeType(1); root.left.left = nodeType(2); root.right = nodeType(3); root.right.left = nodeType(4); root.right.right = nodeType(5); root.right.right.right = nodeType(6); return root; } 0 1 2 3 4 5 6
24. Recursive tree traversal function recursiveTraverse(tree) { // base case if (!tree) return; // recursive case console.log(tree.value); recursiveTraverse(tree.left); recursiveTraverse(tree.right); } > recursiveTraverse(simpleTree); 0 1 2 3 4 5 6
25. Recursive tree traversal function recursiveTraverse(tree) { // base case if (!tree) return; // recursive case console.log(tree.value); recursiveTraverse(tree.left); recursiveTraverse(tree.right); } > recursiveTraverse(simpleTree); 0 1 2 3 4 5 6 in iv e d & w i ! === hu -ef en
26. Iterative tree traversal function iterativeTraverse(tree) { var todo = [tree]; while (todo.length) { var next = todo.shift(); if (next) { console.log(next.value); todo.unshift(next.left); todo.push(next.right); } } } > iterativeTraverse(simpleTree); 0 1 2 3 4 5 6
27. Iterative tree traversal function iterativeTraverse(tree) { var todo = [tree]; while (todo.length) { var next = todo.shift(); if (next) { console.log(next.value); todo.unshift(next.left); todo.push(next.right); } } } > iterativeTraverse(simpleTree); 0 1 2 3 4 5 6 ru j s e l, bu t i t i :/
28. wo n’t o t u t “fo h a of t e…”
29. JS Ite on ES6: • Iterables via [Symbol.iterator] • Iterators via next() • Generators via function* and yield • for…of loops
30. Iterables function iterableTreeNode(value) { let node = { value: value, left: undefined, right: undefined }; function recurseyIterator() { } node[Symbol.iterator]= recurseyIterator; return node; } function recurTraverse(tree) { if (!tree) return; // base case console.log(tree.value); // recursive case recurTraverse(tree.left); recurTraverse(tree.right); } + Recursion
31. Iterables function iterableTreeNode(value) { let node = { value: value, left: undefined, right: undefined }; function recurseyIterator() { } node[Symbol.iterator]= recurseyIterator; return node; } function recurTrav(tree) { console.log(tree.value); // recursive case if (tree.left) recurTrav(tree.left); if (tree.right) recurTrav(tree.right); // base case (no children): just return } + Recursion
32. Iterables function iterableTreeNode(value) { let node = { value: value, left: undefined, right: undefined }; function recurseyIterator() { <output the value> // recursive case <if left, iterate over subtree> <if right, iterate over subtree> // base case: finish iteration } node[Symbol.iterator]= recurseyIterator; return node; } function recurTrav(tree) { console.log(tree.value); // recursive case if (tree.left) recurTrav(tree.left); if (tree.right) recurTrav(tree.right); // base case (no children): just return } + Recursion
33. Iterables function iterableTreeNode(value) { let node = { value: value, left: undefined, right: undefined }; function* recurseyIterator() { yield node.value; // recursive case if (node.left) yield* node.left; if (node.right) yield* node.right; // base case: finish iteration } node[Symbol.iterator]= recurseyIterator; return node; } function recurTrav(tree) { console.log(tree.value); // recursive case if (tree.left) recurTrav(tree.left); if (tree.right) recurTrav(tree.right); // base case (no children): just return } + Recursion
34. Iterables function iterableTreeNode(value) { let node = { value: value, left: undefined, right: undefined }; function* recurseyIterator() { yield node.value; // recursive case if (node.left) yield* node.left; if (node.right) yield* node.right; // base case: finish iteration } node[Symbol.iterator]= recurseyIterator; return node; } > let betterTree = makeTree(iterableTreeNode); > for (let val of betterTree) console.log(val); 0 1 2 3 4 5 6
35. JS It(er) ge b r: github.com/tc39/proposal-async-iteration tc39.github.io/ecma262 • Async Iterables via [Symbol.asyncIterator] • AsyncIterators via next().then() • Async Generators • for await…of loops
36. Iteration JavaScript Recursion = Human-efficient Iteration + +
37. Act II: Rec on, bu r ma
38. Recursion: the dream // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 3 a dream within a dream within a dream within a dream
39. Recursion: the dream // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 3 a dream within a dream within a dream within a dream $ node recursiveInception.js 30 a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream 1 2 3 4 5 6 7 8 9 10 11
40. Recursion: the dream // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 3000 a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a … you get the idea 1 2 3 4 5 6 7 8 9 10 11
41. Recursion: the dream // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 30000 1 2 3 4 5 6 7 8 9 10 11
42. Recursion: the reality // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 30000 /home/anjana/JSHeroes/recursiveInception.js:4 const recursiveInception = (n) => { ^ RangeError: Maximum call stack size exceeded at recursiveInception (recursiveInception.js:4:28) at recursiveInception (recursiveInception.js:6:16) at recursiveInception (recursiveInception.js:6:16) at recursiveInception (recursiveInception.js:6:16) at recursiveInception (recursiveInception.js:6:16) at recursiveInception (recursiveInception.js:6:16) at recursiveInception (recursiveInception.js:6:16) at recursiveInception (recursiveInception.js:6:16) at recursiveInception (recursiveInception.js:6:16) at recursiveInception (recursiveInception.js:6:16) 1 2 3 4 5 6 7 8 9 10 11
43. Recursion: the reality // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 30000 /home/anjana/JSHeroes/recursiveInception.js:4 const recursiveInception = (n) => { ^ RangeError: Maximum call stack size exceeded at recursiveInception (recursiveInception.js:4:28) at recursiveInception (recursiveInception.js:6:16) at recursiveInception (recursiveInception.js:6:16) at recursiveInception (recursiveInception.js:6:16) at recursiveInception (recursiveInception.js:6:16) at recursiveInception (recursiveInception.js:6:16) at recursiveInception (recursiveInception.js:6:16) at recursiveInception (recursiveInception.js:6:16) at recursiveInception (recursiveInception.js:6:16) at recursiveInception (recursiveInception.js:6:16) 1 2 3 4 5 6 7 8 9 10 11
44. Recursion ca s k // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); 1 2 3 4 5 6 7 8 9 10 11
45. Recursion ca s k // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 3 1 2 3 4 5 6 7 8 9 10 11
46. Recursion ca s k // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 3 1 2 3 4 5 6 7 8 9 10 11 ^ s a k (li d e )
47. Recursion ca s k // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 3 1 2 3 4 5 6 7 8 9 10 11 f a > recursiveInception(3) let dreams = recursiveInception(2); return dreams + " within a dream";
48. Recursion ca s k // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 3 1 2 3 4 5 6 7 8 9 10 11 recursiveInception(3) let dreams = recursiveInception(2); return dreams + " within a dream"; recursiveInception(2) let dreams = recursiveInception(1); return dreams + " within a dream"; )^
49. Recursion ca s k // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 3 1 2 3 4 5 6 7 8 9 10 11 recursiveInception(3) let dreams = recursiveInception(2); return dreams + " within a dream"; recursiveInception(2) let dreams = recursiveInception(1); return dreams + " within a dream"; recursiveInception(1) let dreams = recursiveInception(0); return dreams + " within a dream"; )^
50. Recursion ca s k // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 3 1 2 3 4 5 6 7 8 9 10 11 recursiveInception(3) let dreams = recursiveInception(2); return dreams + " within a dream"; recursiveInception(2) let dreams = recursiveInception(1); return dreams + " within a dream"; recursiveInception(1) let dreams = recursiveInception(1); return dreams + " within a dream"; recursiveInception(0) return "a dream"; )^
51. Recursion ca s k // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 3 1 2 3 4 5 6 7 8 9 10 11 recursiveInception(3) let dreams = recursiveInception(2); return dreams + " within a dream"; recursiveInception(2) let dreams = recursiveInception(1); return dreams + " within a dream"; recursiveInception(1) let dreams = recursiveInception(1); return dreams + " within a dream"; recursiveInception(0) return "a dream"; ( ^
52. Recursion ca s k // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 3 1 2 3 4 5 6 7 8 9 10 11 recursiveInception(3) let dreams = recursiveInception(2); return dreams + " within a dream"; recursiveInception(2) let dreams = recursiveInception(1); return dreams + " within a dream"; recursiveInception(1) let dreams = "a dream"; return dreams + " within a dream"; ( ^
53. Recursion ca s k // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 3 1 2 3 4 5 6 7 8 9 10 11 recursiveInception(3) let dreams = recursiveInception(2); return dreams + " within a dream"; recursiveInception(2) let dreams = "a dream within a dream"; return dreams + " within a dream"; ( ^
54. Recursion ca s k // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 3 1 2 3 4 5 6 7 8 9 10 11 recursiveInception(3) let dreams = "a dream within a dream within a dream" ; return dreams + " within a dream"; )^
55. Recursion ca s k // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 3 a dream within a dream within a dream within a dream 1 2 3 4 5 6 7 8 9 10 11
56. Recursion ca s k // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 30000 1 2 3 4 5 6 7 8 9 10 11
57. Recursion ca s k // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 30000 1 2 3 4 5 6 7 8 9 10 11
58. Recursion ca s k // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 30000 1 2 3 4 5 6 7 8 9 10 11 recursiveInception(30000) let dreams=recursiveInception(29999); return dreams + " within a dream";
59. Recursion ca s k // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 30000 1 2 3 4 5 6 7 8 9 10 11 recursiveInception(30000) let dreams=recursiveInception(29999); return dreams + " within a dream"; recursiveInception(29999) let dreams=recursiveInception(29998); return dreams + " within a dream"; )^
60. Recursion ca s k // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 30000 1 2 3 4 5 6 7 8 9 10 11 recursiveInception(30000) let dreams=recursiveInception(29999); return dreams + " within a dream"; recursiveInception(29999) let dreams=recursiveInception(29998); return dreams + " within a dream"; recursiveInception(29998) let dreams=recursiveInception(29997); return dreams + " within a dream"; )^
61. Recursion ca s k // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 30000 1 2 3 4 5 6 7 8 9 10 11 recursiveInception(30000) let dreams=recursiveInception(29999); return dreams + " within a dream"; recursiveInception(29999) let dreams=recursiveInception(29998); return dreams + " within a dream"; recursiveInception(29998) let dreams=recursiveInception(29997); return dreams + " within a dream"; )^ recursiveInception(29997) let dreams=recursiveInception(29996); return dreams + " within a dream";
62. Recursion ca s k // recursiveInception.js 'use strict'; const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } const depth = parseInt(process.argv[2]); console.log(recursiveInception(depth)); $ node recursiveInception.js 30000 RangeError: Maximum call stack size exceeded 1 2 3 4 5 6 7 8 9 10 11 recursiveInception(30000) let dreams=recursiveInception(29999); return dreams + " within a dream"; recursiveInception(29999) let dreams=recursiveInception(29998); return dreams + " within a dream"; recursiveInception(29998) let dreams=recursiveInception(29997); return dreams + " within a dream"; recursiveInception(29997) let dreams=recursiveInception(29996); return dreams + " within a dream"; :(
63. wo n’t o to r e wi t a n t f a s?
64. JS Ta l Op i z i • Implementation feature of (some*) JS engines • Lets us ♻ stack frames: don’t need to “remember” anything from calling context • Requires call in tail position: “proper tail calls” in ES6
65. Tail Recursion const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } f o s e w ^ af r u s al Not -re s e
66. Tail Recursion const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } f o s e w ^ af r u s al Not -re s e const tailRecursiveInception = (n) => { } Ta l-re s e
67. Tail Recursion const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } f o s e w ^ af r u s al Not -re s e const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } Ta l-re s e us e p n ^ to h e r o
68. const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } f o s e w ^ af r u s al Not -re s e const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } Ta l-re s e us e p n ^ to h e r o ^ ca t m a f Tail Recursion
69. const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } f o s e w ^ af r u s al Not -re s e const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } Ta l-re s e us um or ^ to “re b ” hi r Tail Recursion
70. const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } f o s e w ^ af r u s al Not -re s e const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } Ta l-re s e us um or ^ to “re b ” hi r in a c . ^ is ca Tail Recursion
71. const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } f o s e w ^ af r u s al Not -re s e const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } Ta l-re s e ^ re s e l in “ta si ” Tail Recursion
72. const recursiveInception = (n) => { if (n === 0) return "a dream"; let dreams = recursiveInception(n-1); return dreams + " within a dream"; } f o s e w ^ af r u s al Not -re s e const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } Ta l-re s e ^ re s e l la t g f o s Tail Recursion
73. Ta l Op i z i const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } > tailRecursiveInception(3);
74. Ta l Op i z i const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } > tailRecursiveInception(3); tailRecursiveInception(3) return incept(3, "a dream");
75. Ta l Op i z i const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } > tailRecursiveInception(3); tailRecursiveInception(3) return incept(3, "a dream"); )^ incept(3, "a dream") return incept(2, "a dream within a dream");
76. const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } > tailRecursiveInception(3); tailRecursiveInception(3) return incept(3, "a dream"); incept(3, "a dream") return incept(2, "a dream within a dream"); Ta l Op i z i incept(2, "a dream within a dream") return incept(1, "a… w… within a dream"); )^
77. const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } > tailRecursiveInception(3); tailRecursiveInception(3) return incept(3, "a dream"); incept(3, "a dream") return incept(2, "a dream within a dream"); Ta l Op i z i incept(2, "a dream within a dream") return incept(1, "a… w… within a dream"); ♻
78. const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } > tailRecursiveInception(3); tailRecursiveInception(3) return incept(3, "a dream"); incept(2, "a dream within a dream") return incept(1, "a… w… within a dream"); Ta l Op i z i
79. const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } > tailRecursiveInception(3); tailRecursiveInception(3) return incept(3, "a dream"); incept(2, "a dream within a dream") return incept(1, "a… w… within a dream"); Ta l Op i z i )^ incept(1, "a dream within a dream within a dream") return incept(0, "a… w… w… within a dream");
80. const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } > tailRecursiveInception(3); tailRecursiveInception(3) return incept(3, "a dream"); incept(2, "a dream within a dream") return incept(1, "a… w… within a dream"); Ta l Op i z i incept(1, "a dream within a dream within a dream") return incept(0, "a… w… w… within a dream"); ♻
81. const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } > tailRecursiveInception(3); tailRecursiveInception(3) return incept(3, "a dream"); incept(1, "a dream within a dream within a dream") return incept(0, "a… w… w… within a dream"); Ta l Op i z i
82. const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } > tailRecursiveInception(3); tailRecursiveInception(3) return incept(3, "a dream"); incept(1, "a dream within a dream within a dream") return incept(0, "a… w… w… within a dream"); Ta l Op i z i incept(0, "a dream within a dream within a dream within a dream") return "a dream within a dream within a dream within a dream"; )^
83. const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } > tailRecursiveInception(3); tailRecursiveInception(3) return incept(3, "a dream"); incept(1, "a dream within a dream within a dream") return incept(0, "a… w… w… within a dream"); Ta l Op i z i incept(0, "a dream within a dream within a dream within a dream") return "a dream within a dream within a dream within a dream"; ♻
84. const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } > tailRecursiveInception(3); tailRecursiveInception(3) return incept(3, "a dream"); incept(0, "a dream within a dream within a dream within a dream") return "a dream within a dream within a dream within a dream"; Ta l Op i z i
85. const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } > tailRecursiveInception(3); tailRecursiveInception(3) return incept(3, "a dream"); incept(0, "a dream within a dream within a dream within a dream") return "a dream within a dream within a dream within a dream"; ( ^ Ta l Op i z i
86. const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } > tailRecursiveInception(3); tailRecursiveInception(3) return "a dream within a dream within a dream within a dream"; )^ Ta l Op i z i
87. const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } > tailRecursiveInception(3); a dream within a dream within a dream within a dream Ta l Op i z i
88. const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } console.log(tailRecursiveInception(3)); let n = 3; let dreams = "a dream"; while (n > 0) { dreams += " within a dream"; n--; } console.log(dreams); Recursion + T O ≈ Iteration ^ w i t ke s ^ ru s li h
89. T O L // tailRecursiveInception.js 'use strict'; const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } const depth = parseInt(process.argv[2]); console.log(tailRecursiveInception(depth)); 1 2 3 4 5 6 7 8 9 10 11 12 13
90. // tailRecursiveInception.js 'use strict'; const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } const depth = parseInt(process.argv[2]); console.log(tailRecursiveInception(depth)); 1 2 3 4 5 6 7 8 9 10 11 12 13 $ node tailRecursiveInception.js 30000 T O L
91. // tailRecursiveInception.js 'use strict'; const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } const depth = parseInt(process.argv[2]); console.log(tailRecursiveInception(depth)); 1 2 3 4 5 6 7 8 9 10 11 12 13 $ node tailRecursiveInception.js 30000 /home/anjana/JSHeroes/tailRecursiveInception.js:5 const incept = (n, dreams) => { ^ RangeError: Maximum call stack size exceeded at incept (tailRecursiveInception.js:5:18) at incept (tailRecursiveInception.js:7:12) at incept (tailRecursiveInception.js:7:12) at incept (tailRecursiveInception.js:7:12) at incept (tailRecursiveInception.js:7:12) at incept (tailRecursiveInception.js:7:12) at incept (tailRecursiveInception.js:7:12) at incept (tailRecursiveInception.js:7:12) at incept (tailRecursiveInception.js:7:12) at incept (tailRecursiveInception.js:7:12) T O L
92. // tailRecursiveInception.js 'use strict'; const tailRecursiveInception = (n) => { const incept = (n, dreams) => { if (n === 0) return dreams; return incept(n-1, dreams+" within a dream"); } return incept(n, "a dream"); } const depth = parseInt(process.argv[2]); console.log(tailRecursiveInception(depth)); 1 2 3 4 5 6 7 8 9 10 11 12 13 $ node tailRecursiveInception.js 30000 /home/anjana/JSHeroes/tailRecursiveInception.js:5 const incept = (n, dreams) => { ^ RangeError: Maximum call stack size exceeded at incept (tailRecursiveInception.js:5:18) at incept (tailRecursiveInception.js:7:12) at incept (tailRecursiveInception.js:7:12) at incept (tailRecursiveInception.js:7:12) at incept (tailRecursiveInception.js:7:12) at incept (tailRecursiveInception.js:7:12) at incept (tailRecursiveInception.js:7:12) at incept (tailRecursiveInception.js:7:12) at incept (tailRecursiveInception.js:7:12) at incept (tailRecursiveInception.js:7:12) li ! be y ! T O L
93. Ta l Op i z i Feature of (some*) JS engines
94. Ta l Op i z i Feature of (some*) JS engines * On a c e; mo do im m T O kangax.github.io/compat-table/es6/#test-proper_tail_calls_(tail_call_optimisation) • Webkit/Safari has it: webkit.org/blog/6240/ecmascript-6-proper-tail-calls-in-webkit/ • V8/Chromium/Node had it (w/ flag), removed it: bugs.chromium.org/p/v8/issues/detail?id=4698
95. Ta l Op i z i Feature of (some*) JS engines * On a c e; mo do im m T O kangax.github.io/compat-table/es6/#test-proper_tail_calls_(tail_call_optimisation) • Webkit/Safari has it: webkit.org/blog/6240/ecmascript-6-proper-tail-calls-in-webkit/ • V8/Chromium/Node had it (w/ flag), removed it: bugs.chromium.org/p/v8/issues/detail?id=4698 Hot d ed ur ; di s o s o n ! • TCO issues explained in V8 blog: v8project.blogspot.ro/2016/04/es6-es7-and-beyond.html • TC39 proposal for explicit tail call syntax (inactive): github.com/tc39/proposal-ptc-syntax • Ongoing discussion/proposal for WebAssembly: github.com/WebAssembly/tail-call
96. $ nvm use 6 Now using node v6.12.3 T O L
97. $ nvm use 6 Now using node v6.12.3 $ node --harmony_tailcalls tailRecursiveInception.js 30000 T O L
98. $ nvm use 6 Now using node v6.12.3 $ node --harmony_tailcalls tailRecursiveInception.js 30000 a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within a dream within ………………….. T O L
99. Recursion JavaScript Iteration = Machine-efficient Recursion + +
100. Iteration v Recursion
101. JS Iteration Recursion
102. Fur r a n : Exploring JS b D . Axe R c ay exploringjs.com • ES6 - Iteration: Ch. 17, 21, 22; TCO: Ch. 27 • ES2018-ES2019: Asynchronous Iteration MDN developer.mozilla.org • JavaScript>Reference>Iteration_protocols • JavaScript>Guide>Functions>Recursion
103. Mulțum ! JSHeroes organizers & Ioana Chiorean Mapbox The Recurse Center community Max Rabkin @An a V ki ❤ an @ma x.co