Shipsar Tutorials

Recursion in Python

In this module, we'll dive deep into recursion, a powerful concept in programming where a function calls itself to solve smaller instances of a problem. Recursion is often used in problems that involve repetitive tasks or divide-and-conquer approaches.

---

Subtopic 1: Understanding Recursion

Recursion occurs when a function calls itself to solve a problem. It's typically used when a problem can be broken down into smaller, simpler subproblems of the same type.

• Recursive Case: This is the part where the function calls itself with modified parameters, progressively reducing the problem size.
• Base Case: The condition that stops the recursion. Without a base case, recursion would continue indefinitely, leading to a stack overflow.

---

Subtopic 2: Recursive Functions

A recursive function is a function that calls itself to solve a problem. It generally consists of two main parts:

1. Base Case: This is the simplest, smallest instance of the problem that can be solved directly without recursion.
2. Recursive Case: This is the part where the function calls itself with simpler arguments.

Example: Factorial Calculation

The factorial of a number (n) (denoted as (n!)) is the product of all positive integers less than or equal to (n). The factorial of 0 is 1 by definition.

• Recursive Formula: (n! = n \times (n-1)!)

Example:

def factorial(n):
    if n == 0:
        return 1  # Base case: factorial of 0 is 1
    else:
        return n * factorial(n - 1)  # Recursive case

# Example usage
print(factorial(5))  # Output: 120

In the above example:

• The base case is when (n = 0).
• The recursive case calls the function with (n-1).

---

Subtopic 3: Base Cases and Recursive Cases

Understanding the base case and recursive case is crucial in designing a recursive function.

• Base Case: Prevents infinite recursion. Without a base case, the function would call itself indefinitely, resulting in a stack overflow.
• Recursive Case: Breaks the problem down into smaller subproblems, reducing the problem's complexity at each step.

Example: Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. The recursive formula for Fibonacci is: [ F(n) = F(n-1) + F(n-2) ]

Example:

def fibonacci(n):
    if n == 0:
        return 0  # Base case
    elif n == 1:
        return 1  # Base case
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # Recursive case

# Example usage
print(fibonacci(6))  # Output: 8

In the Fibonacci function:

• The base cases are when (n = 0) or (n = 1).
• The recursive case calculates the sum of the previous two Fibonacci numbers.

---

Subtopic 4: Common Recursive Algorithms

Recursion is frequently used in many common algorithms. Here are a few classic examples:

1. Factorial Calculation

The factorial is a basic example of recursion, where the problem is broken down into multiplying the number by the factorial of the previous number.

2. Fibonacci Sequence

The Fibonacci sequence is another classic example of recursion. Each term is the sum of the two preceding terms.

3. Sum of Numbers

Recursion can also be used to calculate the sum of numbers in a list.

Example:

def sum_list(arr):
    if len(arr) == 0:
        return 0  # Base case: empty list
    else:
        return arr[0] + sum_list(arr[1:])  # Recursive case: sum the first element with the rest

# Example usage
print(sum_list([1, 2, 3, 4, 5]))  # Output: 15

---

Tasks

1. Task 1: Factorial Calculation

   • Implement a recursive function to calculate the factorial of a number.
   • Test the function with values from 0 to 10.

2. Task 2: Fibonacci Sequence

   • Write a recursive function to generate the Fibonacci sequence up to a given number (n).
   • Test the function with values of (n) from 0 to 10.

3. Task 3: Sum of List

   • Implement a recursive function that computes the sum of all elements in a list.
   • Test it with various lists (e.g., [1, 2, 3], [10, 20, 30, 40]).

4. Task 4: Tower of Hanoi

   • Implement the recursive solution to the Tower of Hanoi problem, where you have three rods and a number of disks of different sizes.
   • The goal is to move all disks from the first rod to the third, using the second rod, with the constraint that only one disk can be moved at a time, and no disk can be placed on top of a smaller disk.

5. Task 5: Reverse a String

   • Write a recursive function that takes a string and returns it reversed.
   • Example: Input "hello", Output "olleh".

---