Advanced Python · Week 7

Recursion

Step 1 of 5

Exercise 1: Introduction to Recursion

Welcome to Python 2, Lesson 7! Today, we'll learn about recursion, a powerful programming concept where a function calls itself to solve a problem.

What is Recursion?

Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. In programming, recursion occurs when a function calls itself.

Let's start with a simple example of a recursive function that counts down from a given number:

def countdown(n):
    if n <= 0:
        print("Blastoff!")
    else:
        print(n)
        countdown(n - 1)

countdown(5)

Now it's your turn! Create a recursive function called count_up that counts up from 1 to a given number:

Define the function count_up(n)
If n is greater than 5, print "Done!"
Otherwise, print the current number and call count_up(n + 1)
Test your function with count_up(1)

Starter code

# Define your count_up function here

# Test your function
count_up(1)

Write your code here

python

# Define your count_up function here

# Test your function
count_up(1)

Exercise 2: Recursive Functions

Recursive functions are functions that call themselves. They can be very powerful for solving problems that have a recursive nature.

Key Components of a Recursive Function

Base case: The condition that stops the recursion
Recursive case: The part where the function calls itself
Progress towards the base case: Each recursive call should bring us closer to the base case

Let's look at a classic example of a recursive function: calculating the factorial of a number.

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

print(factorial(5))  # Should print 120

Your turn! Create a recursive function to calculate the sum of all numbers from 1 to n:

Define a function called sum_to_n(n)
If n is 1, return 1 (this is the base case)
Otherwise, return n plus the result of calling sum_to_n(n-1)
Test your function with sum_to_n(5) (which should return 15)

Starter code

# Define your sum_to_n function here

# Test your function
print(sum_to_n(5))

Write your code here

python

# Define your sum_to_n function here

# Test your function
print(sum_to_n(5))

Exercise 3: Base Case and Recursive Case

Understanding the base case and recursive case is crucial for writing effective recursive functions.

Base Case vs Recursive Case

Base case: The condition where the function stops calling itself
Recursive case: The condition where the function calls itself with a modified input

Let's look at an example of a recursive function to calculate the nth Fibonacci number:

def fibonacci(n):
    # Base cases
    if n <= 0:
        return "Invalid input"
    elif n == 1 or n == 2:
        return 1
    # Recursive case
    else:
        return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(7))  # Should print 13

Your task: Create a recursive function to calculate the power of a number:

Define a function called power(base, exponent)
If the exponent is 0, return 1 (base case)
Otherwise, return base multiplied by power(base, exponent - 1) (recursive case)
Test your function with power(2, 3) (which should return 8)

Starter code

# Define your power function here

# Test your function
print(power(2, 3))

Write your code here

python

# Define your power function here

# Test your function
print(power(2, 3))

Exercise 4: Recursion vs. Iteration

Many problems can be solved using either recursion or iteration. It's important to understand the trade-offs between these approaches.

Recursion vs. Iteration

Recursion can make code more readable and easier to understand for some problems
Iteration can be more efficient in terms of memory usage
Some problems are naturally recursive and are easier to solve with recursion

Let's compare recursive and iterative approaches to calculating the sum of a list of numbers:

# Recursive approach
def sum_recursive(lst):
    if not lst:
        return 0
    return lst[0] + sum_recursive(lst[1:])

# Iterative approach
def sum_iterative(lst):
    total = 0
    for num in lst:
        total += num
    return total

numbers = [1, 2, 3, 4, 5]
print(sum_recursive(numbers))  # Should print 15
print(sum_iterative(numbers))  # Should print 15

Your task: Implement both a recursive and an iterative function to reverse a string:

Define a function called reverse_recursive(s) that reverses a string recursively
Define a function called reverse_iterative(s) that reverses a string iteratively
Test both functions with the string "hello"

Starter code

# Define your recursive and iterative string reversal functions here

# Test your functions
print(reverse_recursive('hello'))
print(reverse_iterative('hello'))

Write your code here

python

# Define your recursive and iterative string reversal functions here

# Test your functions
print(reverse_recursive('hello'))
print(reverse_iterative('hello'))

Weekly Project: Fractal Tree

Let's put everything we've learned about recursion into practice by creating a fractal tree using the turtle graphics library.

Your task is to create a program that:

Uses the turtle graphics library to draw a fractal tree
Implements a recursive function to draw branches of the tree
Allows customization of the tree's depth and angle

Here's a starting template:

import turtle

def draw_tree(branch_length, angle, depth):
    if depth > 0:
        turtle.forward(branch_length)
        turtle.right(angle)
        draw_tree(branch_length - 15, angle, depth - 1)
        turtle.left(2 * angle)
        draw_tree(branch_length - 15, angle, depth - 1)
        turtle.right(angle)
        turtle.backward(branch_length)

def main():
    turtle.speed(0)  # Set the drawing speed to the fastest
    turtle.left(90)  # Turn the turtle to point upwards
    turtle.up()
    turtle.backward(100)
    turtle.down()
    draw_tree(75, 20, 7)
    turtle.done()

if __name__ == "__main__":
    main()

Enhance the Fractal Tree program by adding the following features:

Add color to the branches (e.g., make them brown)
Add leaves at the end of the smallest branches (e.g., green circles)
Allow user input for the initial branch length, angle, and depth
Experiment with different patterns by changing the angle or length reduction in recursive calls

This project will give you hands-on experience with recursion and visual programming. Have fun and be creative with your fractal tree!

Starter code

# Implement your enhanced Fractal Tree program here

Write your code here

python

# Implement your enhanced Fractal Tree program here

PreviousModules and Scope NextTest