Recursive Algorithms

2.1 File Tree Traversal

Let's look at a recursive algorithm for traversing a file tree. The algorithm will traverse a directory and all its subdirectories, listing all the files and folders.

import os

def list_files_recursive(directory, indent=0):
    # Get a list of all files and folders in the current directory
    items = os.listdir(directory)
                
    for item in items:
        # Create a full path to the file or folder
        path = os.path.join(directory, item)
                    
        # Print with indentation for better understanding of structure
        print(' ' * indent + item)
                    
        # If it's a folder, recursively traverse its contents
        if os.path.isdir(path):
            list_files_recursive(path, indent + 4)
            
# Example usage
root_directory = '/path/to/root/directory'
list_files_recursive(root_directory)

How does it work?

1. Function list_files_recursive(directory, indent=0):
   • directory — the current directory whose contents we want to print.
   • indent — the current level of indentation to show nesting of files and folders.
2. Get a list of all files and folders in the current directory using os.listdir(directory).
3. Iterate over each item in the items list.
4. Create a full path to the item using os.path.join(directory, item).
5. Print the item's name with indentation that increases by 4 spaces for each level of nesting.
6. Check if the item is a folder using os.path.isdir(path). If it is, recursively call list_files_recursive(path, indent + 4) to traverse its contents.

Example output:

Suppose we have the following directory structure:

root_directory/
    file1.txt
    dir1/
        file2.txt
        file3.txt
        dir2/
            file4.txt
    file5.txt

When we run the function list_files_recursive(root_directory), we'll get the following output:

file1.txt
dir1
    file2.txt
    file3.txt
    dir2
        file4.txt
file5.txt

This algorithm recursively traverses the directory tree, printing all files and folders considering their nesting.

2.2 Tower of Hanoi

The "Tower of Hanoi" problem

The Tower of Hanoi is a classic recursive problem that involves moving disks from one peg to another using an auxiliary peg.

Rules:

1. You can move only one disk at a time.
2. A disk can only be placed on an empty peg or on a larger disk.
3. You need to move all disks from one peg to another, using an auxiliary peg.

Here's a recursive algorithm to solve this problem:

The Tower of Hanoi algorithm solves the problem as follows:

1. Move n - 1 disks from the initial peg to the auxiliary peg, using the target peg.
2. Move the remaining disk from the initial peg to the target peg.
3. Move n - 1 disks from the auxiliary peg to the target peg, using the initial peg.

Python example

def hanoi_tower(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    hanoi_tower(n - 1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    hanoi_tower(n - 1, auxiliary, target, source)
        
# Example usage:
n = 3  # Number of disks
hanoi_tower(n, 'A', 'C', 'B')
        

How does it work?

Base case:

If there's only one disk (n == 1), it can be simply moved from the initial peg to the target peg.

if n == 1:
    print(f"Move disk 1 from {source} to {target}")
    return

Recursive case:

Step 1. Move n-1 disks from the initial peg to the auxiliary peg, using the target peg.

hanoi_tower(n - 1, source, auxiliary, target)

Step 2. Move disk n from the initial peg to the target peg.

print(f"Move disk {n} from {source} to {target}")

Step 3. Move n - 1 disks from the auxiliary peg to the target peg, using the initial peg.

hanoi_tower(n - 1, auxiliary, target, source)

Example output:

For three disks (n = 3) on pegs A, B, and C, the program will print:

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

2.3 Koch Snowflake

Drawing a snowflake using recursion is an interesting task, often used to study fractals. One of the simple ways to draw a snowflake is to use the Koch curve, which is a fractal curve.

Algorithm for Drawing a Koch Snowflake

The Koch curve is built as follows:

• Start with a straight line.
• Break each segment into three parts and replace the middle part with a small curve resembling a "corner".
• Repeat this process recursively for each segment.

Step-by-Step Guide

• Start: Draw an initial segment.
• Divide: Divide each segment into three parts.
• Replace the middle part: Draw a "corner" on the middle part, consisting of two lines forming a 60-degree angle.
• Repeat the process: Continue this process for each segment.

Python example using the Turtle library

import turtle

def draw_koch_curve(t, length, depth):
    if depth == 0:
        t.forward(length)
    else:
        length /= 3.0
        draw_koch_curve(t, length, depth - 1)
        t.left(60)
        draw_koch_curve(t, length, depth - 1)
        t.right(120)
        draw_koch_curve(t, length, depth - 1)
        t.left(60)
        draw_koch_curve(t, length, depth - 1)
            
def draw_snowflake(t, length, depth):
    for _ in range(3):
        draw_koch_curve(t, length, depth)
        t.right(120)
            
# Screen setup
screen = turtle.Screen()
screen.bgcolor("sky blue")
            
# Turtle setup
t = turtle.Turtle()
t.speed(0)
t.color("white")
            
# Draw the snowflake
t.penup()
t.goto(-100, 50)
t.pendown()
draw_snowflake(t, 300, 4)
            
# Finish drawing
turtle.done()
            

How does it work?

1. Function draw_koch_curve(t, length, depth):

• t: the turtle doing the drawing.
• length: the length of the segment.
• depth: the depth of recursion, determining the level of detail.

2. Base case:

If depth equals 0, the turtle draws a straight segment.

if depth == 0:
    t.forward(length)
        

3. Recursive case:

Divide the segment into three parts, and apply draw_koch_curve recursively to each part, adding turns.

length /= 3.0
draw_koch_curve(t, length, depth - 1)
t.left(60)
draw_koch_curve(t, length, depth - 1)
t.right(120)
draw_koch_curve(t, length, depth - 1)
t.left(60)
draw_koch_curve(t, length, depth - 1)

4. Function draw_snowflake(t, length, depth):

Draws three Koch curves combined into one snowflake.

for _ in range(3):
    draw_koch_curve(t, length, depth)
    t.right(120)

How to run the code?

• Make sure you have the Turtle library installed (pip install PythonTurtle).
• Copy and paste the code into a .py file and run it. You'll see the snowflake being drawn on the screen.

This algorithm allows for visualizing the fractal structure of a snowflake using simple principles of recursion and geometric constructions.

2

Task

Python SELF EN, level 57, lesson 1

Locked

File tree

File tree

Open

2

Task

Python SELF EN, level 57, lesson 1

Locked

Koch Snowflake

Koch Snowflake

Open