Practice recursion Examples

The best way to master recursion is through practice. Here is a collection of common problems and their recursive solutions.

1. Mathematical Problems

Factorial Calculation

Calculating $n!$ is a classic recursive problem where $n! = n \times (n-1)!$

function factorial(num) {
    if (num <= 1) return 1; // Base case
    return num * factorial(num - 1);
}

Sum of Natural Numbers

Summing numbers from $1$ to $N$.

function sum(n) {
    if (n <= 1) return n;
    return n + sum(n - 1);
}

2. Array Operations

Printing an Array

Recursively moving through indices to print each element.

function printArray(arr, index = 0) {
    if (index >= arr.length) return;
    console.log(arr[index]);
    printArray(arr, index + 1);
}

Summing Array Elements

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

3. Directional Printing

Print N to 1

function printNto1(n) {
    if (n <= 0) return;
    console.log(n);
    printNto1(n - 1);
}

Print 1 to N

function print1toN(n) {
    if (n <= 0) return;
    print1toN(n - 1);
    console.log(n);
}

4. Complexity Patterns

Single Recursive Call

Usually results in Logarithmic or Linear time depending on the reduction.

• $T(n) = T(n/2) + C \implies O(\log n)$
• $T(n) = T(n-1) + C \implies O(n)$

Two Recursive Calls

Usually results in Linear or Exponential complexity.

• $T(n) = 2T(n/2) + C \implies O(n)$
• $T(n) = 2T(n-1) + C \implies O(2^n)$

Conclusion

Use these examples as templates. Most recursive problems can be solved by identifying:

1. What is the smallest possible version of this problem? (Base Case)
2. How can I use the result of a slightly smaller version of the same problem? (Recursive Step)