RecuRun: Recursive Runner Library

Write Recursive, Run Iterative — Write code in a recursive style but execute it iteratively, avoiding stack overflow.

A lightweight, zero-dependency TypeScript library that allows you to write code in a recursive style but execute it iteratively. Say goodbye to stack overflow and embrace infinite recursion!

简体中文 | English

✨ Features

• 🚀 Zero Dependencies - Pure TypeScript implementation
• 🔒 Type Safe - Full TypeScript type support with excellent IDE hints
• ⚡ High Performance - Optimized stack management and call mechanism
• 🛡️ Stable & Reliable - Clear rules, no magic auto-detection
• 📦 Lightweight - < 1KB when minified
• 🧪 Well Tested - 26 comprehensive tests covering all recursion patterns (sync & async)

Installation

npm install recurun
# or
yarn add recurun
# or
pnpm add recurun

Quick Start

🔄 From Normal Recursion to Safe Recursion

Before (Normal recursion - stack overflow on large inputs):

// ❌ Stack overflow on n > 10000
function factorial(n: number, acc: number = 1): number {
    if (n <= 1) return acc;
    return factorial(n - 1, acc * n);
}

After (With RecuRun - handles any depth):

// ✅ No stack overflow, even on n = 100000!
import { runTail } from 'recurun';

function* factorial(n: number, acc: number = 1): Generator<any, number> {
    if (n <= 1) return acc;
    return yield factorial(n - 1, acc * n);  // Just add `yield` keyword!
}

const result = runTail(factorial(100000)); // Works! 🎉

That's it! Just three simple changes:

1. Add function* to make it a generator
2. Add yield before recursive calls
3. Wrap with run() or runTail()

Examples

import { run, runTail } from 'recurun';

// Example 1: Fibonacci sequence (any recursion)
function* fibonacci(n: number): Generator<any, number> {
    if (n <= 2) return 1;
    const a = yield fibonacci(n - 1);
    const b = yield fibonacci(n - 2);
    return a + b;
}

console.log(run(fibonacci(40))); // 102334155

// Example 2: Tail-recursive factorial (with optimization)
function* factorial(n: number, acc: number = 1): Generator<any, number> {
    if (n <= 1) return acc;
    // Note: use yield (not yield*) with runTail
    return yield factorial(n - 1, acc * n);
}

// Can safely calculate very large numbers
console.log(runTail(factorial(100000))); // No stack overflow!

🆕 Async Support

RecuRun now supports async generators (async function*) for handling asynchronous recursive operations!

The API automatically detects async generators - just use run() or runTail():

import { run, runTail } from 'recurun';

// Example: Async Fibonacci
async function* fibonacci(n: number): AsyncGenerator<unknown, number> {
    await new Promise(r => setTimeout(r, 10)); // Simulate async operation
    if (n <= 2) return 1;
    const a = yield fibonacci(n - 1);
    const b = yield fibonacci(n - 2);
    return a + b;
}

console.log(await run(fibonacci(20))); // 6765

// Example: Async Tail Recursion
async function* factorial(n: number, acc: number = 1): AsyncGenerator<unknown, number> {
    await new Promise(r => setTimeout(r, 10)); // Simulate async operation
    if (n <= 1) return acc;
    return yield factorial(n - 1, acc * n);
}

console.log(await runTail(factorial(10000))); // Infinity, no stack overflow!

🔄 Supported Recursion Patterns

RecuRun supports all common recursion patterns:

| Pattern | Description | Status | |---------|-------------|--------| | Linear Recursion | Single recursive call path | ✅ Tested | | Tail Recursion | Recursive call is the last operation | ✅ Optimized (O(1) space) | | Binary Recursion | Two recursive calls (e.g., Fibonacci) | ✅ Tested | | Multi-way Recursion | Three or more recursive calls | ✅ Tested | | Mutual Recursion | Functions calling each other | ✅ Tested | | Nested Recursion | Recursive call as parameter | ✅ Tested | | Conditional Branching | Different recursion paths based on conditions | ✅ Tested | | Tree Traversal | Recursive data structure navigation | ✅ Tested | | Deep Recursion | Depth > 100,000 | ✅ Tested |

Check out test/test.ts for examples of all patterns!

API Documentation

run(generator)

Runs any recursive function using stack simulation to avoid stack overflow. Automatically detects sync/async generators via function overloading.

Use when:

• Multiple recursion branches
• Need to perform operations after recursive calls
• Tree structure traversal

// Sync version
function run<T, TReturn>(generator: Generator<T, TReturn>): TReturn;

// Async version
function run<T, TReturn>(generator: AsyncGenerator<T, TReturn>): Promise<TReturn>;

Example:

import { run } from 'recurun';

// Fibonacci sequence (sync)
function* fib(n: number): Generator<unknown, number> {
  if (n <= 2) return 1;
  const a = yield fib(n - 1);
  const b = yield fib(n - 2);
  return a + b;
}

const result = run(fib(10)); // 55

// Tree traversal (sync)
function* traverse(node: TreeNode): Generator<unknown, number> {
  if (!node) return 0;
  const left = yield traverse(node.left);
  const right = yield traverse(node.right);
  return node.value + left + right;
}

run(traverse(rootTree));

// Async example
async function* fetchAllUsers(ids: number[]): AsyncGenerator<unknown, User[]> {
  if (ids.length === 0) return [];
  const user = await fetchUser(ids[0]);
  const otherUsers = yield fetchAllUsers(ids.slice(1));
  return [user, ...otherUsers];
}

const users = await run(fetchAllUsers([1, 2, 3, 4, 5]));

runTail(generator)

Runs tail-recursive optimized functions, achieving constant-level stack space usage. Automatically detects sync/async generators via function overloading.

Use when:

• Single recursion chain (like factorial, sum)
• Ultra-deep recursion (depth > 10,000)
• Linked list traversal

// Sync version
function runTail<T, TReturn>(generator: Generator<T, TReturn>): TReturn;

// Async version
function runTail<T, TReturn>(generator: AsyncGenerator<T, TReturn>): Promise<TReturn>;

Example:

import { runTail } from 'recurun';

// Tail-recursive factorial (sync)
function* factorial(n: number, acc: number = 1): Generator<unknown, number> {
  if (n <= 1) return acc;
  // Note: use yield (not yield*) - runTail assumes all calls are tail calls
  return yield factorial(n - 1, acc * n);
}

// Can safely calculate huge numbers
const result = runTail(factorial(100000));

// Tail-recursive list traversal (sync)
function* traverseList(list: ListNode): Generator<unknown, number> {
  if (!list) return 0;
  return yield traverseList(list.next);
}

// Async example
async function* processList(list: ListNode): AsyncGenerator<unknown, number> {
  if (!list) return 0;
  await list.loadNext(); // Simulate async operation
  return yield processList(list.next);
}

const result = await runTail(processList(myList));

### `isGenerator(value)`

Checks if a value is a Generator object.

```typescript
function isGenerator(value: any): value is Generator

Example:

function* gen() { yield 1; }
const g = gen();

isGenerator(g);     // true
isGenerator({});     // false
isGenerator(null);   // false

isAsyncGenerator(value)

Checks if a value is an AsyncGenerator object.

function isAsyncGenerator(value: any): value is AsyncGenerator

Example:

async function* gen() { yield 1; }
const g = gen();

isAsyncGenerator(g);     // true
isAsyncGenerator({});     // false
isAsyncGenerator(null);   // false

Performance

⚠️ Performance Trade-offs

Important: RecuRun trades performance for safety. It's slower than normal recursion but prevents stack overflow.

Run the benchmark yourself:

npm run benchmark

Benchmarks

| Test Case | Depth | Normal Recursion | RecuRun | Slowdown | |-----------|-------|------------------|---------|----------| | Fibonacci | 30 | 4.6 ms ✅ | 77.4 ms ✅ | 16.9x ⚠️ | | Factorial | 1,000 | 0.15 ms ✅ | 0.44 ms ✅ | 2.9x ⚠️ | | Tail Factorial | 5,000 | 0.71 ms ✅ | 0.74 ms ✅ | 1.0x ⚠️ | | Array Sum | 5,000 elements | 0.31 ms ✅ | 1.31 ms ✅ | 4.2x ⚠️ | | Deep Recursion | 5,000 | 0.11 ms ✅ | 0.67 ms ✅ | 6.1x ⚠️ | | Very Deep Recursion | 100,000 | ❌ Stack overflow | 8.29 ms ✅ | ∞ ✅ |

Key Takeaways

• Small recursion (< 1,000): RecuRun is 3-17x slower than normal recursion
• Medium recursion (1,000-10,000): RecuRun is 1-6x slower
• Deep recursion (> 10,000): Normal recursion overflows, RecuRun works
• Very deep recursion (> 50,000): Only RecuRun can complete

💡 When to Use RecuRun

| Scenario | Recommendation | Reason | |----------|----------------|--------| | Performance-critical code | ❌ Use normal recursion | Faster execution | | Shallow recursion (< 1,000) | ❌ Use normal recursion | No stack risk, faster | | Deep recursion (> 10,000) | ✅ Use RecuRun | Prevents stack overflow | | Already have stack overflow | ✅ Use RecuRun | Minimal code changes | | Asynchronous recursion | ✅ Use RecuRun | Native async/await support | | Production stability | ✅ Use RecuRun | Predictable, no crashes |

Test environment: Node.js v24, performance may vary by machine and workload

Usage Guide

When to use run?

Use when your recursive function has multiple branches or needs to perform operations after recursive calls:

import { run } from 'recurun';

function* treeSum(node: TreeNode | null): Generator<unknown, number> {
  if (!node) return 0;

  // Need to combine results from two recursive calls
  const leftSum = yield treeSum(node.left);
  const rightSum = yield treeSum(node.right);

  return node.value + leftSum + rightSum;
}

const total = run(treeSum(root));

When to use runTail?

Use when the recursive call is the last operation in your function:

import { runTail } from 'recurun';

function* arraySum(arr: number[], index: number = 0, acc: number = 0): Generator<unknown, number> {
  if (index >= arr.length) return acc;
  // Tail recursive call
  return yield arraySum(arr, index + 1, acc + arr[index]);
}

const sum = runTail(arraySum([1, 2, 3, 4, 5])); // 15

Best Practices

1. Choose the right runner

   // ✅ Correct
   return yield tailRecursive();  // Tail recursion: use runTail
   return (yield normalRecursive()) + x; // Normal recursion: use run

2. Use yield not yield* with runTail

   // ✅ Correct
   function* factorial(n, acc = 1) {
     if (n <= 1) return acc;
     return yield factorial(n - 1, acc * n);  // Use yield
   }
   
   // ❌ Wrong - will cause stack overflow
   function* factorialBad(n, acc = 1) {
     if (n <= 1) return acc;
     return yield* factorialBad(n - 1, acc * n);  // Don't use yield*
   }

3. Be careful with very deep normal recursion

   // ⚠️ Deep binary tree traversal might be slow
   function* deepTree(node: TreeNode) {
     if (!node) return;
     yield deepTree(node.left);   // Each node pushes to stack
     yield deepTree(node.right);
   }

Real-World Examples

Tree Traversal

import { run } from 'recurun';

interface TreeNode {
  value: number;
  left?: TreeNode;
  right?: TreeNode;
}

function* traverse(node: TreeNode | undefined): Generator<unknown, number> {
  if (!node) return 0;
  const leftSum = yield traverse(node.left);
  const rightSum = yield traverse(node.right);
  return node.value + leftSum + rightSum;
}

const total = run(traverse(rootTree));

Linked List Operations

import { runTail } from 'recurun';

interface ListNode {
  value: number;
  next?: ListNode;
}

function* listLength(node: ListNode | undefined, acc: number = 0): Generator<unknown, number> {
  if (!node) return acc;
  return yield listLength(node.next, acc + 1);
}

function* listSum(node: ListNode | undefined, acc: number = 0): Generator<unknown, number> {
  if (!node) return acc;
  return yield listSum(node.next, acc + node.value);
}

const len = runTail(listLength(myList));
const sum = runTail(listSum(myList));

Array Processing

import { run } from 'recurun';

function* arraySum(arr: number[], index = 0): Generator<unknown, number> {
  if (index >= arr.length) return 0;
  return arr[index] + (yield arraySum(arr, index + 1));
}

const total = run(arraySum([1, 2, 3, 4, 5])); // 15

Technical Details

RecuRun uses explicit stack simulation to avoid stack overflow:

1. Standard recursion (run):

   • Maintains an explicit stack array
   • Pushes to stack when yield encounters a generator
   • Pops from stack when generator completes
   • Space complexity: O(n)

2. Tail recursion optimization (runTail):

   • Directly switches generators without creating new stack frames
   • Achieves constant-level stack space usage
   • Space complexity: O(1)

Normal recursion:
fib(5)
  ├─ fib(4)
  │   ├─ fib(3)
  │   │   └─ ...
  │   └─ fib(2)
  └─ fib(3)
      └─ ...

RecuRun (run):
Stack: [fib(5)] → [fib(5), fib(4)] → [fib(5), fib(4), fib(3)] → ...

RecuRun (runTail):
Current: factorial(100000) → factorial(99999) → factorial(99998) → ...
(Stack frame reuse, no growth!)

Comparison with Traditional Trampoline

❌ Traditional Trampoline

// Need to return thunks, code readability is poor
function factorial(n, acc = 1) {
  if (n <= 1) return acc;
  return () => factorial(n - 1, acc * n);  // Return function
}

const trampoline = fn => (...args) => {
  let result = fn(...args);
  while (typeof result === 'function') {
    result = result();
  }
  return result;
};

Problems:

• Need to change coding style, return thunks
• Poor code readability, unintuitive
• Difficult type inference

✅ RecuRun Approach

// Maintain natural recursive writing style!
import { runTail } from 'recurun';

function* factorial(n: number, acc: number = 1): Generator<unknown, number> {
  if (n <= 1) return acc;
  return yield factorial(n - 1, acc * n);  // Natural recursion
}

// Safe calculation, no stack overflow
const result = runTail(factorial(100000));

Advantages:

• Uses Generator's native syntax (yield)
• Maintains intuitive recursive writing
• Complete type inference and IDE support

License

MIT © 2024 RecuRun Team

RecuRun — Write Recursive, Run Iterative. No more stack overflow, just elegant code.

简体中文 | English