Python: Recursion

Introduction

• The power of recursion
• What you should know
• Working with GitHub Codespaces
• A note about file paths

1. Introduction to Recursion

• The concept of recursion
• Why recursion is important

2. The Fundamentals of Recursion

• Exceptions to GitHub Codespaces
• The ingredients of a recursive algorithm
• Recursion in action
• The factorial function: Iterative version
• A recursive factorial function
• Winding and unwinding the call stack in recursion
• Challenge: Fix the recursive algorithm
• Solution: The fundamentals of recursion

3. Classic Recursive Algorithms in Python

• Recursive Fibonacci function in Python
• Recursive sum function in Python
• Recursive greatest common divisor function in Python

4. Practice Writing Recursive Algorithms in Python

• Recursive multiplication algorithm in Python
• Recursive exponentiation algorithm in Python
• String length recursive algorithm

5. Sorting Data Using Recursion in Python

• Introduction to quicksort
• Coding the quicksort algorithm in Python
• Challenge: Check your understanding of quicksort
• Solution: Check your understanding of quicksort

6. Data Traversal Using Recursion

• Traversing a Linked List using recursion
• Traversing a tree using recursion: Overview
• Traversing a tree using recursion: Python implementation
• Challenge: Tree traversal
• Solution: Tree traversal

7. Optimizing Recursion in Python

• Memory considerations with recursive algorithms
• Memoization in Python
• Tail call optimization in Python

8. Drawing Fractals Using Recursion in Python

• H-tree fractal using Python Turtle graphics
• Sierpinski triangle

9. The Towers of Hanoi: A Classic Recursive Puzzle

• Introduction to the Towers of Hanoi puzzle
• Coding the Towers of Hanoi puzzle in Python

Conclusion

• Recursion vs. iteration
• Conclusion