Objective

In this unit, we will explore the concept of recursion, a powerful programming technique where a function calls itself to solve a problem. Recursion can be used to create elegant solutions for complex problems. By the end of this unit, you will understand how to use recursion in Python and apply it to create complex patterns with the Turtle library.

Understanding Recursion

Recursion is a method where the solution to a problem depends on solutions to smaller instances of the same problem. A recursive function is one that calls itself, either directly or indirectly, in order to accomplish its task. Recursion is often used in problems that can be broken down into smaller, similar sub-problems.

Base Case and Recursive Case

A recursive function typically has two parts:

1. Base Case: The condition under which the recursion stops. This prevents the function from calling itself indefinitely.
2. Recursive Case: The part of the function where the recursion occurs, calling itself on a smaller instance of the problem.

Examples of Recursion

Recursion can be used to solve various problems, such as calculating factorials, synthesizing fractals, generating Fibonacci sequences, and more. It's particularly powerful in problems that can be divided into smaller sub-problems of the same type.

Factorial Example

The factorial of a non-negative integer $n$ is the product of all positive integers less than or equal to $n$. It is denoted by $n!$. For example, the factorial of 5 is:

$5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$.

Here's the code for calculating the factorial of a number using recursion:

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

print(factorial(5)) # prints 120

The function factorial takes an integer $n$ as input and returns the factorial of that number. The function is defined recursively, meaning it calls itself within its definition.

Base Case

If $n$ is 1, the function returns 1. This is the base case, and it's essential for stopping the recursion. Without a base case, the function would call itself indefinitely.

Recursive Case

If $n$ is greater than 1, the function returns $n$ times the factorial of $(n - 1)$. This is where the recursion happens. The function calls itself with a smaller value of $n$, and this process continues until the base case is reached.

Here's how the function calculates the factorial of 5:

1. factorial(5) returns $5 \times \text{factorial}(4)$
2. factorial(4) returns $4 \times \text{factorial}(3)$
3. factorial(3) returns $3 \times \text{factorial}(2)$
4. factorial(2) returns $2 \times \text{factorial}(1)$
5. factorial(1) returns 1 (base case)
6. Substituting back, we get $5 \times 4 \times 3 \times 2 \times 1 = 120$

The recursive calls build up a chain of pending multiplications, and once the base case is reached, the multiplications are carried out as the recursive calls are resolved.

Recursion vs Iteration

Recursion and iteration (using loops) are two ways to repeat code. While they can often be used interchangeably, they have different characteristics:

• Recursion: Often more concise and can be more intuitive for certain problems. However, it can be less efficient in terms of memory usage.
• Iteration: Generally more efficient in terms of memory but can be more verbose.

Choosing between recursion and iteration depends on the specific problem and the requirements of the code.

Project: Draw a Fractal Using Recursion and the Turtle Library

Let's use recursion to draw a fractal tree using the Turtle library:

import turtle

# Define a recursive function to draw the tree
def draw_tree(branch_length):
    if branch_length > 5:  # Base case
        turtle.forward(branch_length)
        turtle.right(20)
        draw_tree(branch_length - 15)  # Recursive case
        turtle.left(40)
        draw_tree(branch_length - 15)  # Recursive case
        turtle.right(20)
        turtle.backward(branch_length)

# Set turtle speed to fastest
turtle.speed(0)

# Initilize the turtle direction to point up (positive y direction)
turtle.left(90)

# Draw the tree
draw_tree(100)

# Wait until the window is closed
turtle.done()

The code creates a fractal tree by repeatedly drawing branches and subtrees at decreasing lengths and alternating angles. The recursive nature of the function allows it to draw a complex tree structure with relatively simple code. The base case ensures that the recursion stops at a certain depth, and the recursive cases create the branching structure of the tree.

Base Case

The base case for the recursion is when the branch_length is less than or equal to 5. If this condition is met, the function simply returns without drawing anything. This ensures that the recursion eventually stops, and it also creates the "leaves" of the tree by not drawing very small branches.

Recursive Case

If the branch_length is greater than 5, the function performs the following steps:

1. Draw the Branch: The turtle moves forward by branch_length units, drawing the current branch of the tree.

2. Draw the Right Subtree:

   • The turtle turns right by 20 degrees, creating an angle for the right subtree.
   • The function calls itself recursively with branch_length - 15, drawing the right subtree. This reduces the length of the branches as the recursion goes deeper, creating the smaller branches at the ends of the tree.

3. Draw the Left Subtree:

   • The turtle turns left by 40 degrees (undoing the previous 20-degree right turn and then turning left by an additional 20 degrees), creating an angle for the left subtree.
   • The function calls itself recursively with branch_length - 15, drawing the left subtree.

4. Return to the Starting Position:

   • The turtle turns right by 20 degrees, undoing the previous left turn.
   • The turtle moves backward by branch_length units, returning to the starting position of the current branch. This ensures that the turtle is in the correct position to continue drawing the rest of the tree.

In the next unit, we'll learn how to split a Python program into multiple files, modules, and libraries, enhancing the organization and reusability of code.