Lesson 3: Recursion

In this lesson, we will dive deep into the concept of Recursion, one of the most important topics in programming. Recursion is a technique where a function calls itself in order to solve a problem. This approach is especially useful when a problem can be broken down into smaller, similar subproblems.

We will cover the following topics in detail:

• Understanding Recursion
• Base Case and Recursive Case
• Examples and Problems

1. Understanding Recursion

Recursion is a concept where a function solves a problem by calling itself. The key idea is that a complex problem can be divided into smaller subproblems that are easier to solve. These subproblems resemble the original problem but are simpler in nature.

In a recursive function, there are two essential components:

• Recursive case: The part where the function calls itself to solve smaller subproblems.
• Base case: The condition that stops the recursion. If the base case is not defined, the function would keep calling itself infinitely, leading to a stack overflow

Recursive Structure:

• Problem: We can divide the problem into smaller versions of the same problem.
• Solution: We solve the smaller versions of the problem and combine them to form the solution to the original problem.

Recursion is particularly helpful when working with problems that have a naturally hierarchical or nested structure, such as tree traversal, searching, sorting, and mathematical calculations like the Fibonacci sequence or factorial.

2. Base Case and Recursive Case

A recursive function generally has two parts:

• Base case: The simplest instance of the problem, which can be directly solved without further recursion. This ensures the recursion will eventually stop.
• Recursive case: The part where the function calls itself with a simplified version of the original problem.

Base Case

The base case acts as the termination condition for the recursion. If the base case is not reached, the recursion will continue indefinitely, causing a program crash.

Recursive Case

The recursive case reduces the problem into a smaller subproblem, and calls the function on this reduced problem. Each recursive call moves the problem closer to the base case.

Example: A simple recursive function to calculate the factorial of a number.

Factorial of a number (n!):

• The factorial of a number nis defined as:
  • n! = n × (n – 1) × (n – 2) × … × 1for n > 1
  • 0! = 1(base case)

In recursive terms, we can define the factorial function as:

• Base Case: factorial(0) = 1
• Recursive Case: factorial(n) = n × factorial(n – 1)for n > 0

Python Code:

Explanation:

• The base caseis when n equals 0, in which case the function returns 1 because 0! = 1.
• The recursive caseoccurs when n > 0. The function calls itself with the value n – 1 and multiplies it by n.

Example Calculation:

Let’s compute factorial(4):

3. Examples and Problems

To better understand recursion, let’s go through some classic problems and their recursive solutions:

a. Fibonacci Sequence

The Fibonacci sequence is defined as:

• F(0) = 0
• F(1) = 1
• F(n) = F(n – 1) + F(n – 2)for n > 1

Python Code:

Explanation:

• The base cases are fibonacci(0) = 0and fibonacci(1) = 1.
• The recursive case calculates the Fibonacci number as the sum of the previous two Fibonacci numbers (fibonacci(n – 1)and fibonacci(n – 2)).

b. Sum of Elements in a List

Suppose you have a list of numbers, and you want to calculate the sum of all elements. Recursion can be used to sum the list elements by breaking down the problem into smaller subproblems.

Python Code:

Explanation:

• The base caseis when the list is empty (len(lst) == 0), at which point the sum is 0.
• The recursive caseadds the first element of the list (lst[0]) to the result of the recursive call on the rest of the list (lst[1:]).

c. Reverse a String

We can use recursion to reverse a string by breaking it down into smaller substrings and swapping them.

Python Code:

Explanation:

• The base caseis when the string has only one character or is empty. In this case, the string is already reversed.
• The recursive casetakes the first character (s[0]) and appends it to the reversed substring (reverse_string(s[1:])).

d. Tower of Hanoi Problem

This is a classic example of a recursive problem. In the Tower of Hanoi, the objective is to move a stack of disks from one rod to another, following a set of rules. We will focus on the recursive nature of the problem.

Problem:

• Move ndisks from source pole A to destination pole C using an auxiliary pole B.
• Only one disk can be moved at a time.
• No disk can be placed on top of a smaller disk.

Python Code:

Explanation:

• The base caseis when there is only one disk to move (n == 1). It can be moved directly to the destination.
• The recursive caseinvolves:
  1. Moving n-1disks from the source pole to the auxiliary pole.
  2. Moving the largest disk (n) to the destination pole.
  3. Moving the n-1disks from the auxiliary pole to the destination pole.

4. Conclusion

In this lesson, we learned about Recursion, a powerful technique for solving problems that can be broken down into smaller, similar subproblems. Key points include:

• Recursive function: A function that calls itself to solve smaller instances of the same problem.
• Base case: A condition that stops the recursion to avoid infinite loops.
• Recursive case: The part where the function calls itself with a simplified version of the problem.

Recursion is a natural fit for problems like the Fibonacci sequence, factorial, string reversal, and sorting. However, it’s important to ensure that the base case is properly defined to avoid infinite recursion.

Understanding recursion will enable you to solve complex problems with elegant and simple solutions.