Advanced Recursion Types

Beyond basic direct recursion, several other structural patterns exist to solve complex problems.

Tree Recursion

In Tree Recursion, a function makes more than one recursive call within its body. This forms a tree-like structure of function calls.

Example: Fibonacci Prediction

Stock market analysts or biologists often use Fibonacci-like sequences where a value depends on two previous values.

function tree(n) {
    if (n <= 0) return;
    
    console.log(n);
    tree(n - 1); // 1st call
    tree(n - 1); // 2nd call
}

[!NOTE] Tree recursion typically has exponential time complexity $O(2^n)$ because the number of calls doubles at each level.

Indirect Recursion

In Indirect Recursion, two or more functions call each other in a circular manner.

Example: Parent-Child Interaction

A child asks to go out, the parent asks about homework, and the cycle continues until the homework is done.

function childAsk(n) {
    if (n > 0) {
        console.log(` Child: Can I go outside? (${n})`);
        parentResponse(n - 1); // Calls parent
    } else {
        console.log(" Child: Yay! ");
    }
}
 
function parentResponse(n) {
    if (n > 0) {
        console.log(` Parent: Finish homework first! (${n})`);
        childAsk(n - 2); // Calls child
    }
}

Nested Recursion

In Nested Recursion, a recursive function is passed as an argument to another recursive call of the same function (fun(fun(n))).

Example: Unpacking Layered Gifts

Imagine a gift wrapped in layers where unwrapping one layer reveals another layer that itself needs multiple unwraps.

function nested(n) {
    if (n > 100) {
        return n - 10;
    }
    return nested(nested(n + 11)); // Recursion within recursion
}
 
console.log(nested(95)); // Output: 91

Summary of Types