TypeScriptrecursion.ts
Copy
1
// Fibonacci with memoisation
2
const memo = new Map<number, number>();
3
function fib(n: number): number {
4
  if (n <= 1) return n;
5
  if (memo.has(n)) return memo.get(n)!;
6
  const result = fib(n - 1) + fib(n - 2);
7
  memo.set(n, result);
8
  return result;
9
}
10
 
11
// Tree traversal
12
type TreeNode = { val: number; left?: TreeNode; right?: TreeNode };
13
 
14
function inOrder(node: TreeNode | undefined): number[] {
15
  if (!node) return [];
16
  return [...inOrder(node.left), node.val, ...inOrder(node.right)];
17
}
18
 
19
// Iterative inOrder (avoids call stack limit for deep trees)
20
function inOrderIterative(root: TreeNode | undefined): number[] {
21
  const result: number[] = [], stack: TreeNode[] = [];
22
  let curr: TreeNode | undefined = root;
23
  while (curr || stack.length) {
24
    while (curr) { stack.push(curr); curr = curr.left; }
25
    curr = stack.pop()!;
26
    result.push(curr.val);
27
    curr = curr.right;
28
  }
29
  return result;
30
}
31
 
32
// Flatten arbitrary nested array
33
function flatten(arr: any[]): any[] {
34
  return arr.reduce((flat, item) =>
35
    flat.concat(Array.isArray(item) ? flatten(item) : item), []);
36
}
37
 
38
console.log(fib(40));   // 102334155
39
console.log(flatten([1, [2, [3, [4]]]]));  // [1, 2, 3, 4]