Data Structures and Algorithms

by Albert Major

Functions and Recursion

1. Functions Overview:
   • Good functions:
     • Have no unintended side effects.
     • Are reusable, modular, and self-contained.
   • Functions decompose problems into smaller, manageable tasks.
2. Recursion Basics:
   • A function that calls itself to solve smaller instances of the same problem.
   • Requires:
     • Base case: A simple condition where the recursion stops.
     • Recursive case: Breaks the problem into smaller sub-problems.
   • Example: Factorial.
     • Base Case: 0! = 1.
     • Recursive Case: n! = n * (n-1)!.
3. Recursion vs. Iteration:
   • Recursion is easier for problems like tree traversal or Tower of Hanoi.
   • Iteration is usually faster and more memory-efficient.
   • Be cautious of stack overflow in deep recursions.

Examples and Exercises

1. Factorial Example:

   • Recursive solution:

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

   • Iterative solution:

     def factorial_iterative(n):
         result = 1
         for i in range(1, n + 1):
             result *= i
         return result
     

2. Tower of Hanoi:

   • Problem: Move all disks from one pole to another with rules:

     • Only one disk can be moved at a time.
     • Larger disks cannot be placed on smaller disks.

   • Recursive solution:

     • Move n-1 disks to the intermediate pole.
     • Move the largest disk to the target pole.
     • Move the n-1 disks from the intermediate pole to the target pole.

   • Example code:

     def hanoi(n, start, end, temp):
         if n == 0:
             return
         hanoi(n - 1, start, temp, end)
         print(f"Move disk {n} from {start} to {end}")
         hanoi(n - 1, temp, end, start)
     

3. Exercises:

   • Implement Towers of Hanoi for any number of disks.
   • Count the number of moves.
   • Design an iterative solution for the Towers of Hanoi.