recursion practice problems

New Era

3 min read

·

19-10-2024

56

0

Share

Dive Deep into Recursion: A Practice Problem Playground

Recursion, the art of defining a function in terms of itself, can feel like a mind-bending concept at first. However, mastering this powerful technique opens up a world of elegant and efficient solutions to complex problems.

This article will guide you through a series of practice problems, designed to solidify your understanding of recursion. Each problem comes with a solution, but the real learning happens when you try to solve it yourself before peeking at the answer. Let's get started!

Problem 1: Factorial Calculation

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.

Write a recursive function to calculate the factorial of a given number.

Solution:

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

print(factorial(5)) # Output: 120 

Explanation:

• Base Case: When n is 0, the factorial is 1. This is the base case that stops the recursion.
• Recursive Case: For any other value of n, the factorial is calculated by multiplying n with the factorial of (n-1). This step recursively calls the function until the base case is reached.

Problem 2: Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones. The sequence starts with 0 and 1. For example: 0, 1, 1, 2, 3, 5, 8, 13, ...

Write a recursive function to generate the nth Fibonacci number.

Solution:

def fibonacci(n):
  if n <= 1:
    return n
  else:
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(7)) # Output: 13

Explanation:

• Base Cases: The first two Fibonacci numbers are 0 and 1.
• Recursive Case: For n greater than 1, the nth Fibonacci number is calculated by adding the (n-1)th and (n-2)th Fibonacci numbers.

Problem 3: Tower of Hanoi

The Tower of Hanoi is a classic puzzle that involves three rods and a set of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a stack of decreasing size on one rod, the "source" rod. The goal of the puzzle is to move the entire stack to another rod, the "destination" rod, obeying the following simple rules:

1. Only one disk can be moved at a time.
2. A larger disk may not be placed on top of a smaller disk.

Write a recursive function to solve the Tower of Hanoi puzzle.

Solution:

def tower_of_hanoi(n, source, destination, auxiliary):
  if n == 1:
    print("Move disk 1 from", source, "to", destination)
  else:
    tower_of_hanoi(n - 1, source, auxiliary, destination)
    print("Move disk", n, "from", source, "to", destination)
    tower_of_hanoi(n - 1, auxiliary, destination, source)

tower_of_hanoi(3, 'A', 'C', 'B') 

Explanation:

• Base Case: If there is only one disk (n=1), simply move it from the source rod to the destination rod.
• Recursive Case:
  1. Move the top (n-1) disks from the source rod to the auxiliary rod using the destination rod as an intermediary.
  2. Move the largest disk (n) from the source rod to the destination rod.
  3. Move the (n-1) disks from the auxiliary rod to the destination rod using the source rod as an intermediary.

Additional Challenges:

• Binary Search: Implement a recursive binary search function to find a target element in a sorted array.
• Palindrome Check: Write a recursive function to determine if a string is a palindrome (reads the same backward as forward).
• Tree Traversal: Explore different recursive tree traversal techniques like pre-order, in-order, and post-order traversal.

Remember: Recursion is a powerful tool, but it's crucial to understand the base case and the recursive step to ensure your function terminates correctly. Practice these problems and explore more recursion challenges to master this fundamental concept in programming.

Attribution: The code examples in this article are adapted from various GitHub repositories and user contributions. All code contributions are credited to their respective authors.