Programming Entry Level: examples recursion – ██FR█████ █INTELL███████████

This content originally appeared on DEV Community and was authored by DevOps Fundamental

Understanding Recursion for Beginners

Have you ever tried to explain something by referring to itself? That’s kind of what recursion is! It’s a powerful programming technique that can seem a little mind-bending at first, but once you grasp the core idea, it opens up a whole new way of solving problems. Understanding recursion is also a common topic in technical interviews, so it’s a great skill to have in your toolbox.

2. Understanding Recursion

Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Think of it like Russian nesting dolls (Matryoshka dolls). Each doll contains a smaller version of itself, and to get to the smallest doll, you have to open each one in turn.

In programming, a recursive function is a function that calls itself within its own definition. It’s crucial that a recursive function has two main parts:

Base Case: This is the condition that stops the recursion. Without a base case, the function would call itself infinitely, leading to a stack overflow error (think of an infinite loop!). It’s like the smallest doll in the Matryoshka set – you can’t open it further.
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 one inside.

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;

This diagram shows that a function call checks for a base case. If the base case is 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 calculate the factorial using recursion in Python:

def factorial(n):
  """
  Calculates the factorial of a non-negative integer.
  """
  if n == 0:  # Base case: factorial of 0 is 1

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

    return n * factorial(n-1)

# Example usage:

result = factorial(5)
print(result)  # Output: 120

Let’s break down this code:

def factorial(n): defines a function called factorial that takes an integer n as input.
if n == 0: checks if n is equal to 0. This is our base case. If n is 0, the function returns 1 because the factorial of 0 is 1.
else: If n is not 0, the function executes the recursive step.
return n * factorial(n-1): This line calculates the factorial by multiplying n with the factorial of n-1. Notice that the factorial function is calling itself with a smaller input (n-1). This continues until n becomes 0, hitting the base case.

Here’s how the function calls unfold for factorial(5):

factorial(5) returns 5 * factorial(4)
factorial(4) returns 4 * factorial(3)
factorial(3) returns 3 * factorial(2)
factorial(2) returns 2 * factorial(1)
factorial(1) returns 1 * factorial(0)
factorial(0) returns 1 (base case)

Then, the values are returned back up the chain:

factorial(1) returns 1 * 1 = 1
factorial(2) returns 2 * 1 = 2
factorial(3) returns 3 * 2 = 6
factorial(4) returns 4 * 6 = 24
factorial(5) returns 5 * 24 = 120

4. Common Mistakes or Misunderstandings

Here are some common pitfalls to avoid when working with recursion:

Incorrect code (Missing Base Case):

def factorial(n):
  return n * factorial(n-1)

Corrected code:

def 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 infinitely, leading to a stack overflow error.

Incorrect code (Incorrect Recursive Step):

def factorial(n):
  if n == 0:
    return 1
  else:
    return factorial(n) # Calling with the same input!

Corrected code:

def factorial(n):
  if n == 0:
    return 1
  else:
    return n * factorial(n-1)

Explanation: The recursive step needs to move closer to the base case. Calling factorial(n) again doesn’t change the input and will also lead to infinite recursion.

Incorrect code (Complex Base Case):

def factorial(n):
  if n > 1:
    return n * factorial(n-1)
  else:
    return 1

Corrected code:

def factorial(n):
  if n == 0:
    return 1
  else:
    return n * factorial(n-1)

Explanation: While this works, it’s better to have the base case be the simplest possible condition. n == 0 is clearer and more direct than n > 1.

5. Real-World Use Case

Let’s imagine you want to calculate the sum of all numbers in a list. You could do this with a loop, but let’s use recursion!

def sum_list(numbers):
  """
  Calculates the sum of all numbers in a list using recursion.
  """
  if not numbers:  # Base case: empty list has a sum of 0

    return 0
  else:  # Recursive step: sum = first element + sum of the rest of the list

    return numbers[0] + sum_list(numbers[1:])

# Example usage:

my_list = [1, 2, 3, 4, 5]
total = sum_list(my_list)
print(total)  # Output: 15

In this example:

if not numbers: checks if the list is empty. If it is, the base case is reached, and the function returns 0.
else: If the list is not empty, the function returns the sum of the first element (numbers[0]) and the sum of the rest of the list (sum_list(numbers[1:])). numbers[1:] creates a new list containing all elements except the first one.

6. Practice Ideas

Here are a few exercises to help you practice recursion:

Calculate the power of a number: Write a recursive function to calculate x raised to the power of n (xⁿ).
Reverse a string: Write a recursive function to reverse a given string.
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).
Count down: Write a recursive function that takes a number as input and prints numbers from that number down to 1.
Find the maximum value in a list: Write a recursive function to find the largest number in a list.

7. Summary

Congratulations! You’ve taken your first steps into the world of recursion. You’ve learned what recursion is, how it works, and how to write simple recursive functions. Remember the key ingredients: 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 you’ll gradually become more comfortable with this powerful technique. Next, you might want to explore more complex recursive algorithms like tree traversals or divide-and-conquer strategies. Keep coding, and have fun!

This content originally appeared on DEV Community and was authored by DevOps Fundamental