JavaScript 18 🧬 what is recursion

Recursion is a programming technique where a function calls itself directly or indirectly to solve smaller instances of the same problem. It’s a powerful approach for problems that can be broken down into smaller, similar sub-problems.

---

A Quick Look at the Examples

// 1. Factorial
function factorial(n) {
    if (n === 0 || n === 1) return 1; // Base case
    return n * factorial(n - 1);       // Recursive case
}
console.log(factorial(5)); // 120

// 2. Tree Traversal
function traverseTree(node) {
    if (node === null) return;
    console.log(node.value);
    traverseTree(node.left);
    traverseTree(node.right);
}

// 3. Fibonacci with Memoization
const memo = {};
function fibonacci(n) {
    if (n <= 1) return n;
    if (!memo[n]) {
        memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    }
    return memo[n];
}
console.log(fibonacci(7)); // 13

// 4. Fractal (recursive drawing)
function drawFractal(ctx, x, y, length, angle, depth) {
    if (depth === 0) return;
    const radians = (Math.PI / 180) * angle;
    const endX = x + length * Math.cos(radians);
    const endY = y - length * Math.sin(radians);
    ctx.beginPath();
    ctx.moveTo(x, y);
    ctx.lineTo(endX, endY);
    ctx.stroke();
    drawFractal(ctx, endX, endY, length * 0.75, angle + 20, depth - 1);
    drawFractal(ctx, endX, endY, length * 0.75, angle - 20, depth - 1);
}

// 5. Quick Sort
function quickSort(arr) {
    if (arr.length <= 1) return arr;
    const pivot = arr[Math.floor(arr.length / 2)];
    const left = [];
    const right = [];
    for (let i = 0; i < arr.length; i++) {
        if (i === Math.floor(arr.length / 2)) continue;
        if (arr[i] < pivot) left.push(arr[i]);
        else right.push(arr[i]);
    }
    return [...quickSort(left), pivot, ...quickSort(right)];
}
console.log(quickSort([3, 6, 8, 10, 1, 2, 1])); // [1, 1, 2, 3, 6, 8, 10]

---

a. Recursion

Recursion is a programming technique where a function calls itself directly or indirectly to solve smaller instances of the same problem.

Critical: It’s important to include a base case in recursive functions to prevent infinite recursion — which leads to a stack overflow error.

Basic Structure of a Recursive Function

Part	Description
1. Base Case	A condition that stops the recursion
2. Recursive Case	The function calls itself with a modified argument to solve a smaller problem

function recursiveFunction(input) {
    if (baseCondition) {
        return baseResult; // BASE CASE — stop here
    }
    // RECURSIVE CASE — call itself with smaller input
    return recursiveFunction(modifiedInput);
}

---

Advantages of Recursion

Advantage	Description
Simplicity	Recursive solutions can be more concise and easier to understand for problems that naturally fit a recursive pattern
Readability	For certain problems, recursion makes code more readable by directly mirroring the problem’s structure

---

Disadvantages of Recursion

Disadvantage	Description
Performance Overhead	Each function call adds a new layer to the call stack — increased memory usage and slower performance for deep recursions
Stack Overflow	Excessive recursion can cause a stack overflow error if the maximum call stack size is exceeded
Debugging Difficulty	Debugging recursive functions can be more challenging due to multiple layers of function calls

---

b. Recursion Examples

Common Use Cases

#	Use Case	Description
1	Tree Traversal	Recursion is often used to traverse tree-like data structures
2	Dynamic Programming	Recursive solutions can be optimized using memoization or tabulation
3	Fractals and Graphics	Recursion can generate complex patterns and shapes
4	Sorting Algorithms	Algorithms like quicksort and mergesort use recursion

---

Example 1: Factorial

The factorial of n (written n!) is the product of all positive integers up to n.

5! = 5 × 4 × 3 × 2 × 1 = 120

function factorial(n) {
    if (n === 0 || n === 1) {
        return 1; // Base case
    }
    return n * factorial(n - 1); // Recursive case
}
console.log(factorial(5)); // 120

How it works:

factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1        ← base case returns 1
= 120

---

Example 2: Tree Traversal

Recursion is natural for tree structures — each node has children that are themselves trees.

function traverseTree(node) {
    if (node === null) return; // Base case

    console.log(node.value); // Process current node

    traverseTree(node.left);  // Traverse left subtree
    traverseTree(node.right); // Traverse right subtree
}

Tree structure:

        A
       / \
      B   C
     / \   \
    D   E   F

Traversal order: A → B → D → E → C → F (pre-order)

Why recursion works here: Each subtree is a smaller tree — the same problem applied to a smaller input.

---

Example 3: Fibonacci with Memoization

The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

const memo = {};

function fibonacci(n) {
    if (n <= 1) return n; // Base case

    if (!memo[n]) {
        memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    }

    return memo[n];
}
console.log(fibonacci(7)); // 13

Without memoization: fibonacci(7) would make ~41 function calls
With memoization: Only ~8 function calls (each number computed once)

Memoization = caching results to avoid redundant calculations.

---

Example 4: Fractals (Recursive Graphics)

Recursion can generate self-similar patterns — like trees, snowflakes, and fractals.

function drawFractal(ctx, x, y, length, angle, depth) {
    if (depth === 0) return; // Base case

    const radians = (Math.PI / 180) * angle;
    const endX = x + length * Math.cos(radians);
    const endY = y - length * Math.sin(radians);

    ctx.beginPath();
    ctx.moveTo(x, y);
    ctx.lineTo(endX, endY);
    ctx.stroke();

    // Recursive calls — each branch spawns two smaller branches
    drawFractal(ctx, endX, endY, length * 0.75, angle + 20, depth - 1);
    drawFractal(ctx, endX, endY, length * 0.75, angle - 20, depth - 1);
}

Each level branches into 2 smaller branches — creating a tree-like fractal.

---

Example 5: Quick Sort

Quick sort divides the array into smaller sub-arrays, sorts them recursively, and combines them.

function quickSort(arr) {
    if (arr.length <= 1) return arr; // Base case

    const pivot = arr[Math.floor(arr.length / 2)];
    const left = [];
    const right = [];

    for (let i = 0; i < arr.length; i++) {
        if (i === Math.floor(arr.length / 2)) continue;
        if (arr[i] < pivot) left.push(arr[i]);
        else right.push(arr[i]);
    }

    return [...quickSort(left), pivot, ...quickSort(right)];
}

console.log(quickSort([3, 6, 8, 10, 1, 2, 1])); // [1, 1, 2, 3, 6, 8, 10]

How it works:

1. Pick a pivot (middle element)
2. Partition into left (smaller) and right (larger)
3. Recursively sort left and right
4. Combine: [...sortedLeft, pivot, ...sortedRight]

---

Tail Recursion

Tail recursion is a special case where the recursive call is the last operation in the function.

// ❌ Not tail recursive — multiplication happens after the call
function factorial(n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1); // Multiplication AFTER recursion
}

// ✅ Tail recursive — recursive call is the last operation
function factorialTail(n, accumulator = 1) {
    if (n <= 1) return accumulator;
    return factorialTail(n - 1, n * accumulator); // Call is the last thing
}

Why it matters: Some languages optimize tail recursion to avoid stack growth — but JavaScript does not (as of ES2023). You still risk stack overflow with deep tail recursion.

---

Complete Example

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Recursion</title>
    <style>
        body {
            font-family: 'Segoe UI', Tahoma, Geneva, Verdana, sans-serif;
            max-width: 800px;
            margin: 0 auto;
            padding: 20px;
            background: #f8f9fa;
            color: #333;
            line-height: 1.6;
        }
        h1 { color: #007bff; border-bottom: 3px solid #007bff; padding-bottom: 10px; }
        h2 { color: #28a745; border-left: 4px solid #28a745; padding-left: 15px; margin-top: 30px; }
        .demo-box {
            background: white;
            padding: 20px;
            border-radius: 8px;
            box-shadow: 0 2px 10px rgba(0, 0, 0, 0.1);
            margin: 15px 0;
        }
        pre {
            background: #1e1e1e;
            color: #d4d4d4;
            padding: 15px;
            border-radius: 8px;
            overflow-x: auto;
            font-family: 'Courier New', monospace;
            font-size: 0.9rem;
            line-height: 1.8;
        }
        .keyword { color: #569cd6; }
        .string { color: #ce9178; }
        .number { color: #b5cea8; }
        .function { color: #dcdcaa; }
        .comment { color: #6a9955; }
        .boolean { color: #569cd6; }
        #output {
            background: #e9ecef;
            padding: 15px;
            border-radius: 8px;
            margin-top: 15px;
            min-height: 40px;
            font-family: 'Courier New', monospace;
            font-size: 0.85rem;
            border-left: 4px solid #007bff;
            white-space: pre-wrap;
        }
        table {
            width: 100%;
            border-collapse: collapse;
            margin: 15px 0;
        }
        th, td {
            padding: 10px;
            border: 1px solid #ddd;
            text-align: left;
        }
        th { background: #007bff; color: white; }
        tr:nth-child(even) { background: #f8f9fa; }
        .btn {
            padding: 10px 20px;
            background: #007bff;
            color: white;
            border: none;
            border-radius: 6px;
            font-size: 1em;
            font-weight: bold;
            cursor: pointer;
            margin: 5px;
            transition: all 0.3s;
        }
        .btn:hover {
            background: #0056b3;
            transform: translateY(-2px);
        }
        .btn-success { background: #28a745; }
        .btn-success:hover { background: #1e7e34; }
        canvas {
            border: 2px solid #ddd;
            border-radius: 8px;
            background: white;
            display: block;
            margin: 15px auto;
        }
        .input-group {
            margin: 10px 0;
        }
        .input-group label {
            display: inline-block;
            min-width: 150px;
            font-weight: bold;
        }
        .input-group input {
            padding: 8px 12px;
            border: 2px solid #ddd;
            border-radius: 6px;
            font-size: 1em;
            width: 100px;
        }
        .input-group input:focus {
            outline: none;
            border-color: #007bff;
        }
    </style>
</head>
<body>

    <h1>Recursion</h1>

    <div class="demo-box">
        <h2>1. Factorial</h2>
        <pre>
<span class="keyword">function</span> <span class="function">factorial</span>(n) {
    <span class="keyword">if</span> (n === <span class="number">0</span> || n === <span class="number">1</span>) {
        <span class="keyword">return</span> <span class="number">1</span>; <span class="comment">// Base case</span>
    }
    <span class="keyword">return</span> n * <span class="function">factorial</span>(n - <span class="number">1</span>); <span class="comment">// Recursive case</span>
}
console.log(<span class="function">factorial</span>(<span class="number">5</span>)); <span class="comment">// 120</span>
        </pre>
    </div>

    <div class="demo-box">
        <h2>2. Interactive: Factorial Calculator</h2>
        <div class="input-group">
            <label for="factorialInput">Enter a number:</label>
            <input type="number" id="factorialInput" min="0" max="20" value="5">
        </div>
        <button class="btn btn-success" onclick="calculateFactorial()">Calculate Factorial</button>
        <div id="factorialOutput"></div>
    </div>

    <div class="demo-box">
        <h2>3. Interactive: Fibonacci Sequence</h2>
        <div class="input-group">
            <label for="fibonacciInput">How many numbers?</label>
            <input type="number" id="fibonacciInput" min="1" max="20" value="10">
        </div>
        <button class="btn" onclick="showFibonacci()">Show Sequence</button>
        <div id="fibonacciOutput"></div>
    </div>

    <div class="demo-box">
        <h2>4. Recursive Fractal Tree</h2>
        <p>A fractal drawn recursively — each branch spawns two smaller branches.</p>
        <canvas id="fractalCanvas" width="700" height="400"></canvas>
        <div style="text-align: center;">
            <button class="btn" onclick="drawTree()">🌳 Draw Tree</button>
        </div>
    </div>

    <div class="demo-box">
        <h2>5. Recursive Quick Sort</h2>
        <div class="input-group">
            <label for="arrayInput">Array (comma-separated):</label>
            <input type="text" id="arrayInput" value="3, 6, 8, 10, 1, 2, 1" style="width: 250px;">
        </div>
        <button class="btn btn-success" onclick="sortArray()">Sort</button>
        <div id="sortOutput"></div>
    </div>

    <div class="demo-box">
        <h2>6. Live Output — Recursion Examples</h2>
        <div id="output">Loading...</div>
    </div>

    <script>
        // ============================================
        // Recursion — Live Demo
        // ============================================

        let results = [];

        // 1. Factorial
        results.push('📌 Factorial:\n');

        function factorial(n) {
            if (n === 0 || n === 1) return 1;
            return n * factorial(n - 1);
        }

        results.push('  factorial(0) → ' + factorial(0));
        results.push('  factorial(1) → ' + factorial(1));
        results.push('  factorial(5) → ' + factorial(5));
        results.push('  factorial(10) → ' + factorial(10));
        results.push('');

        // 2. Fibonacci with memoization
        results.push('📌 Fibonacci (with Memoization):\n');
        const memo = {};

        function fibonacci(n) {
            if (n <= 1) return n;
            if (!memo[n]) {
                memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
            }
            return memo[n];
        }

        const fibSequence = [];
        for (let i = 0; i < 10; i++) {
            fibSequence.push(fibonacci(i));
        }
        results.push('  First 10 Fibonacci numbers:');
        results.push('  [' + fibSequence.join(', ') + ']');
        results.push('  fibonacci(20) → ' + fibonacci(20));
        results.push('');

        // 3. Sum of array
        results.push('📌 Recursive Sum:\n');

        function sumArray(arr, index = 0) {
            if (index === arr.length) return 0; // Base case
            return arr[index] + sumArray(arr, index + 1);
        }

        const numbers = [1, 2, 3, 4, 5];
        results.push('  sumArray([' + numbers.join(', ') + ']) → ' + sumArray(numbers));
        results.push('');

        // 4. Countdown
        results.push('📌 Recursive Countdown:\n');

        function countdown(n) {
            if (n <= 0) {
                return ['Go!'];
            }
            return [n, ...countdown(n - 1)];
        }

        results.push('  countdown(5) → [' + countdown(5).join(', ') + ']');
        results.push('');

        // 5. Reverse a string
        results.push('📌 Recursive String Reverse:\n');

        function reverseString(str) {
            if (str.length <= 1) return str;
            return reverseString(str.slice(1)) + str[0];
        }

        results.push('  reverseString("hello") → "' + reverseString("hello") + '"');
        results.push('  reverseString("recursion") → "' + reverseString("recursion") + '"');
        results.push('');

        // 6. Power function
        results.push('📌 Recursive Power:\n');

        function power(base, exponent) {
            if (exponent === 0) return 1;
            return base * power(base, exponent - 1);
        }

        results.push('  power(2, 10) → ' + power(2, 10));
        results.push('  power(3, 4) → ' + power(3, 4));
        results.push('');

        // 7. Quick sort
        results.push('📌 Quick Sort:\n');

        function quickSort(arr) {
            if (arr.length <= 1) return arr;
            const pivot = arr[Math.floor(arr.length / 2)];
            const left = [];
            const right = [];
            for (let i = 0; i < arr.length; i++) {
                if (i === Math.floor(arr.length / 2)) continue;
                if (arr[i] < pivot) left.push(arr[i]);
                else right.push(arr[i]);
            }
            return [...quickSort(left), pivot, ...quickSort(right)];
        }

        const unsorted = [3, 6, 8, 10, 1, 2, 1];
        results.push('  quickSort([' + unsorted.join(', ') + '])');
        results.push('  → [' + quickSort([...unsorted]).join(', ') + ']');
        results.push('');

        // 8. Stack overflow demonstration
        results.push('📌 Stack Overflow (Caught):\n');

        let depth = 0;
        function infiniteRecursion() {
            depth++;
            infiniteRecursion();
        }

        try {
            infiniteRecursion();
        } catch (e) {
            results.push('  Caught: ' + e.name + ' — ' + e.message);
            results.push('  Reached depth: ~' + depth);
        }
        results.push('  💡 Always include a base case!');

        document.getElementById('output').textContent = results.join('\n');

        // ============================================
        // Interactive Functions
        // ============================================

        function calculateFactorial() {
            const n = Number(document.getElementById('factorialInput').value);
            const output = document.getElementById('factorialOutput');

            if (n < 0 || n > 20) {
                output.innerHTML = '<p style="color: #dc3545;">Please enter a number between 0 and 20.</p>';
                return;
            }

            const result = factorial(n);
            output.innerHTML = `<p><strong>${n}!</strong> = ${result.toLocaleString()}</p>`;

            // Show the calculation steps
            let steps = [];
            for (let i = n; i >= 1; i--) {
                steps.push(i);
            }
            output.innerHTML += `<p style="font-size: 0.85rem; color: #6c757d;">
                ${steps.join(' × ')} = ${result.toLocaleString()}</p>`;
        }

        function showFibonacci() {
            const count = Number(document.getElementById('fibonacciInput').value);
            const output = document.getElementById('fibonacciOutput');

            if (count < 1 || count > 20) {
                output.innerHTML = '<p style="color: #dc3545;">Please enter a number between 1 and 20.</p>';
                return;
            }

            const sequence = [];
            for (let i = 0; i < count; i++) {
                sequence.push(fibonacci(i));
            }

            output.innerHTML = `<p>Fibonacci sequence (${count} numbers):</p>
                <p style="font-family: 'Courier New', monospace; font-size: 1.1em; color: #007bff;">
                ${sequence.join(', ')}</p>`;
        }

        function sortArray() {
            const input = document.getElementById('arrayInput').value;
            const output = document.getElementById('sortOutput');
            const arr = input.split(',').map(n => Number(n.trim())).filter(n => !isNaN(n));

            if (arr.length === 0) {
                output.innerHTML = '<p style="color: #dc3545;">Please enter valid numbers.</p>';
                return;
            }

            const sorted = quickSort([...arr]);

            output.innerHTML = `<p>Original: <code>[${arr.join(', ')}]</code></p>
                <p>Sorted:   <code style="color: #28a745;">[${sorted.join(', ')}]</code></p>`;
        }

        // ============================================
        // Fractal Tree Drawing
        // ============================================

        const canvas = document.getElementById('fractalCanvas');
        const ctx = canvas.getContext('2d');

        function drawTree() {
            ctx.clearRect(0, 0, canvas.width, canvas.height);

            // Draw starting from bottom-center
            drawBranch(canvas.width / 2, canvas.height, 100, -90, 10);
        }

        function drawBranch(x, y, length, angle, depth) {
            if (depth === 0) return;

            const radians = (Math.PI / 180) * angle;
            const endX = x + length * Math.cos(radians);
            const endY = y + length * Math.sin(radians);

            // Color based on depth
            const hue = 120 + (10 - depth) * 15;
            ctx.strokeStyle = `hsl(${hue}, 70%, ${40 + depth * 2}%)`;
            ctx.lineWidth = depth / 2;

            ctx.beginPath();
            ctx.moveTo(x, y);
            ctx.lineTo(endX, endY);
            ctx.stroke();

            // Recursive branches
            drawBranch(endX, endY, length * 0.75, angle + 20, depth - 1);
            drawBranch(endX, endY, length * 0.75, angle - 20, depth - 1);
        }

        // Draw tree on load
        drawTree();

        // Run initial calculations
        calculateFactorial();
        showFibonacci();
        sortArray();
    </script>

</body>
</html>

---

Quick Reference

Basic Structure

Part	Description
Base Case	Stops the recursion
Recursive Case	Calls itself with smaller input

---

Advantages vs Disadvantages

Advantages	Disadvantages
✅ Concise, elegant code	❌ Performance overhead
✅ Natural for tree/graph problems	❌ Stack overflow risk
✅ Mirrors mathematical definitions	❌ Harder to debug
✅ Reduces code duplication	❌ More memory usage

---

Common Use Cases

Use Case	Example
Tree Traversal	DOM, file systems, JSON
Dynamic Programming	Fibonacci, knapsack
Fractals & Graphics	Koch snowflake, Sierpinski triangle
Sorting Algorithms	Quick sort, merge sort
Mathematical	Factorial, power, GCD
Backtracking	N-Queens, maze solving

---

Best Practices

✅ Do This:

// Always include a base case
function factorial(n) {
    if (n <= 1) return 1; // ✅ Base case FIRST
    return n * factorial(n - 1);
}

// Ensure progress toward the base case
function countdown(n) {
    if (n <= 0) return;
    console.log(n);
    countdown(n - 1); // ✅ Decreases n each call
}

// Use memoization for expensive recursive calls
const memo = {};
function fib(n) {
    if (n <= 1) return n;
    if (memo[n]) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

// Consider iteration for deep recursion
function sumIterative(n) {
    let total = 0;
    for (let i = 1; i <= n; i++) total += i;
    return total;
}

❌ Don’t Do This:

// Don't forget the base case
function infinite(n) {
    return infinite(n - 1); // ❌ Stack overflow!
}

// Don't recurse without progress
function stuck(n) {
    if (n === 0) return;
    return stuck(n); // ❌ Same argument — infinite!
}

// Don't use recursion for simple loops
function sum(n) {
    if (n === 0) return 0;
    return n + sum(n - 1); // OK, but a for loop is more efficient
}

// Don't use recursion for large depth without memoization
function slowFib(n) {
    if (n <= 1) return n;
    return slowFib(n - 1) + slowFib(n - 2); // ❌ Exponential time!
}

---

Common Pitfalls

Pitfall	Problem	Solution
Missing base case	Infinite recursion	Always include base case
No progress	Infinite recursion	Modify argument each call
Deep recursion	Stack overflow	Use iteration or increase stack
No memoization	Exponential time	Cache results
Incorrect base case	Wrong results	Verify with test cases

---

Recursion vs Iteration

Aspect	Recursion	Iteration
Readability	✅ Elegant for tree/graph problems	❌ Can be verbose
Performance	❌ Slower, more memory	✅ Faster, less memory
Stack	❌ Limited depth	✅ No stack limit
Use for	Trees, backtracking, divide & conquer	Simple loops, large data

---

Pro Tip: Recursion is elegant for problems that naturally break into smaller sub-problems — trees, fractals, divide-and-conquer algorithms. But it comes at a cost: each call adds to the stack, so deep recursion can cause a stack overflow. Always include a base case to stop the recursion, and ensure each call makes progress toward the base case. For expensive recursion like Fibonacci, use memoization to cache results. And when in doubt: iteration is often more efficient — use recursion when it makes the code clearer, not just cleverer!

---

Stop using slow, ad-bloated tool sites! 🤮

🔎 Search “KandZ Tools” on Google to use many professional utilities for free.

KandZ.me is the ultimate minimalist hub for:
✅ Finance (Mortgage, Interest, Inflation)
✅ Tech (Base64, JSON, Dev Suite, IP)
✅ Health (BMI, BMR, TDEE)
✅ Productivity (Timer, Workspace, QR)

⚡️ Fast & Private
🔒 No data leaves your device
💎 100% Free

🔗 Use it now: https://tools.kandz.me
🔖 Bookmark it—you’ll need it later!