Programming Entry Level: how to recursion

Understanding how to Recursion for Beginners

Have you ever tried to solve a problem by breaking it down into smaller, similar problems? That's the core idea behind recursion! It's a powerful programming technique that can seem a little mind-bending at first, but once you grasp the concept, it opens up a whole new way of thinking about problem-solving. Recursion is a common topic in technical interviews, and understanding it will make you a more versatile programmer.

2. Understanding "how to recursion"

Imagine you have a set of Russian nesting dolls (Matryoshka dolls). Each doll contains a smaller version of itself, until you get to the smallest doll that doesn't contain any others. Recursion is similar!

A recursive function is a function that calls itself within its own definition. It's like opening a Matryoshka doll – you perform the same action (opening the doll) on a smaller version of the problem (the smaller doll inside).

Every recursive function needs two key parts:

1. Base Case: This is the condition that stops the recursion. It's like the smallest Matryoshka doll – it doesn't contain another doll, so you stop opening. Without a base case, the function would call itself forever, leading to a stack overflow error (think of it as an infinite loop!).
2. Recursive Step: This is where the function calls itself with a modified input, bringing it closer to the base case. It's like opening a doll to reveal a smaller doll – you're performing the same action on a smaller problem.

Here's a simple way to visualize it using a mermaid diagram:

graph TD
    A[Function Call] --> B{Base Case?};
    B -- Yes --> C[Return Value];
    B -- No --> D[Recursive Call with Modified Input];
    D --> A;

The diagram shows that the function checks for the base case. If it's met, it returns a value. Otherwise, it makes a recursive call with a modified input, and the process repeats.

3. Basic Code Example

Let's look at a classic example: calculating the factorial of a number. The factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example, 5! = 5 * 4 * 3 * 2 * 1 = 120.

Here's how we can implement this recursively in JavaScript:

function factorial(n) {
  // Base case: factorial of 0 is 1
  if (n === 0) {
    return 1;
  } else {
    // Recursive step: n! = n * (n-1)!
    return n * factorial(n - 1);
  }
}

console.log(factorial(5)); // Output: 120

Let's break down this code:

1. function factorial(n): This defines a function named factorial that takes an integer n as input.
2. if (n === 0): This is the base case. If n is 0, the function returns 1 (because 0! = 1).
3. else: If n is not 0, the function executes the recursive step.
4. return n * factorial(n - 1): This is the recursive step. It returns n multiplied by the factorial of n - 1. Notice that the function calls itself with a smaller input (n - 1).

Now, let's look at the same example in Python:

def factorial(n):
  # Base case: factorial of 0 is 1

  if n == 0:
    return 1
  else:
    # Recursive step: n! = n * (n-1)!

    return n * factorial(n - 1)

print(factorial(5)) # Output: 120

The logic is identical to the JavaScript example, just with Python syntax.

4. Common Mistakes or Misunderstandings

Here are some common mistakes beginners make when learning recursion:

❌ Incorrect code (Missing Base Case):

function factorial(n) {
  return n * factorial(n - 1);
}

✅ Corrected code:

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

Explanation: This code is missing a base case. Without it, the function will call itself indefinitely, leading to a stack overflow error.

❌ Incorrect code (Not Moving Towards Base Case):

function factorial(n) {
  if (n === 0) {
    return 1;
  } else {
    return n * factorial(n + 1); // Incorrect: Adding instead of subtracting
  }
}

✅ Corrected code:

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

Explanation: The recursive step should move the input closer to the base case. In this example, we're adding 1 instead of subtracting, so the function will never reach the base case.

❌ Incorrect code (Incorrect Base Case Value):

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

✅ Corrected code:

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

Explanation: While this might work for some inputs, the correct base case for factorial is n === 0. Using n === 1 can lead to incorrect results for factorial(0).

5. Real-World Use Case

Let's create a simple function to calculate the sum of all elements in an array recursively.

function sumArray(arr) {
  // Base case: empty array
  if (arr.length === 0) {
    return 0;
  } else {
    // Recursive step: sum of first element + sum of the rest of the array
    return arr[0] + sumArray(arr.slice(1));
  }
}

const numbers = [1, 2, 3, 4, 5];
console.log(sumArray(numbers)); // Output: 15

In this example:

1. sumArray(arr) takes an array arr as input.
2. The base case is when the array is empty (arr.length === 0). In this case, the function returns 0.
3. The recursive step adds the first element of the array (arr[0]) to the sum of the rest of the array (sumArray(arr.slice(1))). arr.slice(1) creates a new array containing all elements except the first one.

6. Practice Ideas

Here are some exercises to help you practice recursion:

1. Calculate the power of a number: Write a recursive function to calculate x^n (x to the power of n).
2. Reverse a string: Write a recursive function to reverse a given string.
3. Fibonacci sequence: Write a recursive function to calculate the nth Fibonacci number. (Remember the Fibonacci sequence starts with 0 and 1, and each subsequent number is the sum of the previous two).
4. Count down: Write a recursive function that takes a number as input and prints numbers from that number down to 1.
5. Find the maximum value in an array: Write a recursive function to find the largest number in an array.

7. Summary

Congratulations! You've taken your first steps into the world of recursion. You've learned that recursion involves breaking down a problem into smaller, similar subproblems and solving them using a function that calls itself. Remember the importance of a base case to stop the recursion and a recursive step to move closer to the base case.

Don't be discouraged if it doesn't click immediately. Recursion takes practice! Keep experimenting with different examples and exercises. Next, you might want to explore more advanced topics like tail recursion and memoization to optimize your recursive functions. Keep coding, and have fun!