Understanding Recursion in JavaScript: Forward vs Backward Recursion

Recursion is a fundamental concept in programming where a function calls itself to solve a problem. It’s commonly used in scenarios like tree traversal, searching, and mathematical computations. In this blog, we’ll explore two types of recursion in JavaScript: Forward Recursion and Backward Recursion.

What is Recursion?

Recursion is a technique where a function solves a problem by calling itself with modified parameters until it reaches a base condition that stops further calls. A recursive function consists of:

1. Base Case: The stopping condition to prevent infinite recursion.

2. Recursive Case: The part where the function calls itself with updated arguments.

Example: Printing Numbers Using Recursion

Let’s consider a simple example where we print numbers from 0 to 10 using recursion.

Forward Recursion (Top-Down Approach)

function printNnumber(n) {
    if (n > 10) return; // Base case

    console.log(n); // Print before recursive call
    printNnumber(n + 1);
}

printNnumber(0);

How it Works?

1. The function starts at n = 0.

2. It prints the current number before making a recursive call.

3. The function keeps calling itself, increasing n by 1.

4. When n reaches 11, the base case stops further recursion.

Output:

0
1
2
3
4
5
6
7
8
9
10

Backward Recursion (Bottom-Up Approach)

function printNnumber(n) {
    if (n > 10) return; // Base case

    printNnumber(n + 1); // Recursive call before printing
    console.log(n); // Print after recursive call
}

printNnumber(0);

How it Works?

1. The function starts at n = 0 but does not print immediately.

2. It keeps calling itself until n = 11, where it stops.

3. Once recursion starts returning, numbers get printed in reverse order.

Output:

10
9
8
7
6
5
4
3
2
1
0

Key Differences Between Forward and Backward Recursion

When to Use Which?

Forward Recursion Use Cases:

1. Tree Traversals (Preorder): Visiting the root before its children.

2. Printing an array in order: Traversing from first to last element.

3. Factorial Calculation: Multiplying numbers in ascending order.

4. Solving Maze Problems: Making a move before checking further.

Backward Recursion Use Cases:

1. Tree Traversals (Postorder): Visiting children before the root.

2. Reversing an array: Processing the last element first.

3. Computing Fibonacci Numbers: Solving the subproblems before using them.

4. Backtracking Algorithms: Exploring all possibilities before making decisions.

• Forward Recursion Questions:

  1. Write a function to print an array in order using recursion.

  2. Implement a function to find the sum of an array using recursion.

  3. Solve the factorial of a number using forward recursion.

  4. Implement a recursive function to count the number of digits in a number.

Backward Recursion Questions:

1. Write a function to print an array in reverse using recursion.

2. Implement a function to compute Fibonacci numbers using backward recursion.

3. Solve a problem where you need to reverse a linked list using recursion.

4. Implement a recursive function to check if a string is a palindrome.

Conclusion

Recursion is a powerful technique in programming, and understanding how forward and backward recursion work helps in writing efficient and optimized solutions. Knowing when to use each type of recursion can make a big difference in problem-solving.

Happy coding! 🚀