We use cookies to enhance your experience on the site
Recursion - Nested Caves
Congratulations, @name! You've reached the last lesson of Module 2!
Imagine exploring nested caves in the jungle. You enter the first cave, find a passage to the second cave, there you find a passage to the third... and so on. To return, you must retrace your steps exactly the same way - exit the third, then the second, then the first.
This is recursion - a function calls itself, creating "nested" calls, and then "unwinds" back through all of them.
What Is Recursion?
Recursion is a programming technique where a function calls itself in its own definition.
Key elements of recursion:
- Base case - the stopping condition
- Recursive case - the call to itself
- Progress toward base case - each call gets closer to the base case
1def countdown(n):
2 """Simple recursion example"""
3 # Base case - stop the recursion
4 if n <= 0:
5 print("Start!")
6 return
7
8 # Recursive case - call itself
9 print(n)
10 countdown(n - 1) # Call with a smaller value (progress!)
11
12countdown(5)
13# Output:
14# 5
15# 4
16# 3
17# 2
18# 1
19# Start!How Recursion Works - Call Stack
Python uses the call stack to manage recursion:
1def factorial(n):
2 """Factorial: n! = n × (n-1) × (n-2) × ... × 1"""
3 print(f"Calling factorial({n})")
4
5 if n <= 1:
6 print(f"Base case! Returning 1")
7 return 1
8
9 result = n * factorial(n - 1) # Recursion!
10 print(f"Returning {n} * factorial({n-1}) = {result}")
11 return result
12
13print(f"\nResult: {factorial(5)}\n")
14
15# Call stack:
16# factorial(5) -> waits for factorial(4)
17# factorial(4) -> waits for factorial(3)
18# factorial(3) -> waits for factorial(2)
19# factorial(2) -> waits for factorial(1)
20# factorial(1) -> returns 1 (base case!)
21# factorial(2) -> returns 2 * 1 = 2
22# factorial(3) -> returns 3 * 2 = 6
23# factorial(4) -> returns 4 * 6 = 24
24# factorial(5) -> returns 5 * 24 = 120Recursion vs Iteration
Most recursive problems can be solved iteratively (with loops):
1# Recursion
2def factorial_recursive(n):
3 """O(n) time, O(n) memory (call stack)"""
4 if n <= 1:
5 return 1
6 return n * factorial_recursive(n - 1)
7
8# Iteration
9def factorial_iterative(n):
10 """O(n) time, O(1) memory"""
11 result = 1
12 for i in range(1, n + 1):
13 result *= i
14 return result
15
16# Both return the same result
17print(factorial_recursive(5)) # 120
18print(factorial_iterative(5)) # 120When to use recursion?
- ✅ The problem has a recursive nature (trees, graphs, divide-and-conquer)
- ✅ The code becomes simpler and more readable
- ✅ The recursion depth is limited (won't exceed the stack limit)
When to use iteration?
- ✅ The problem is naturally iterative
- ✅ Memory efficiency is crucial
- ✅ The depth can be very large
Classic Recursion Examples
1. Factorial
1def factorial(n):
2 """
3 n! = n × (n-1)!
4 Base case: 0! = 1, 1! = 1
5 """
6 if n <= 1:
7 return 1
8 return n * factorial(n - 1)
9
10print(factorial(0)) # 1
11print(factorial(1)) # 1
12print(factorial(5)) # 120
13print(factorial(10)) # 36288002. Fibonacci Sequence
1def fibonacci(n):
2 """
3 fib(n) = fib(n-1) + fib(n-2)
4 Base cases: fib(0) = 0, fib(1) = 1
5 """
6 if n <= 0:
7 return 0
8 if n == 1:
9 return 1
10 return fibonacci(n - 1) + fibonacci(n - 2)
11
12# First 10 Fibonacci numbers
13for i in range(10):
14 print(f"fib({i}) = {fibonacci(i)}")
15# 0, 1, 1, 2, 3, 5, 8, 13, 21, 34WARNING: Naive Fibonacci is O(2^n) - very slow! Use memoization:
1# With memoization (caching results)
2def fibonacci_memo(n, memo={}):
3 """O(n) with memoization!"""
4 if n in memo:
5 return memo[n]
6
7 if n <= 0:
8 return 0
9 if n == 1:
10 return 1
11
12 memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
13 return memo[n]
14
15# Much faster!
16print(fibonacci_memo(50)) # 12586269025 (instantly!)3. Sum of List Elements
1def sum_list(arr):
2 """
3 Sum a list recursively
4 Base case: empty list -> 0
5 Recursive: first element + sum of the rest
6 """
7 if not arr: # Empty list
8 return 0
9 return arr[0] + sum_list(arr[1:])
10
11print(sum_list([1, 2, 3, 4, 5])) # 15
12print(sum_list([])) # 0
13
14# Safari example
15discovered_sizes = [1.5, 2.3, 3.1, 1.8, 4.2] # meters
16total_size = sum_list(discovered_sizes)
17print(f"Total size of discovered species: {total_size}m") # 12.9m4. Reversing a String
1def reverse_string(s):
2 """
3 Reverse a string recursively
4 Base case: empty string or 1 character
5 Recursive: last character + reversed rest
6 """
7 if len(s) <= 1:
8 return s
9 return s[-1] + reverse_string(s[:-1])
10
11print(reverse_string("Python")) # nohtyP
12print(reverse_string("Safari")) # irafaS
13
14# Alternative version (first + rest)
15def reverse_string_v2(s):
16 if len(s) <= 1:
17 return s
18 return reverse_string_v2(s[1:]) + s[0]
19
20print(reverse_string_v2("Darwin")) # niwraD5. Checking for Palindrome
1def is_palindrome(s):
2 """
3 Check if a string is a palindrome recursively
4 Palindrome: reads the same forwards and backwards (e.g., "racecar")
5 """
6 # Remove spaces and convert to lowercase
7 s = s.replace(" ", "").lower()
8
9 # Base cases
10 if len(s) <= 1:
11 return True
12
13 # Check first and last characters
14 if s[0] != s[-1]:
15 return False
16
17 # Check the middle recursively
18 return is_palindrome(s[1:-1])
19
20print(is_palindrome("racecar")) # True
21print(is_palindrome("Python")) # False
22print(is_palindrome("A man a plan a canal Panama")) # True
23print(is_palindrome("level")) # TrueBinary Search - Recursively
1def binary_search_recursive(arr, target, left=0, right=None):
2 """
3 Binary search - O(log n)
4
5 arr: sorted list
6 target: value to find
7 left, right: search range
8 """
9 if right is None:
10 right = len(arr) - 1
11
12 # Base case - not found
13 if left > right:
14 return -1
15
16 # Check the middle
17 mid = (left + right) // 2
18
19 if arr[mid] == target:
20 return mid # Found!
21 elif arr[mid] < target:
22 # Search in the right half
23 return binary_search_recursive(arr, target, mid + 1, right)
24 else:
25 # Search in the left half
26 return binary_search_recursive(arr, target, left, mid - 1)
27
28# Safari example
29species = ["Elephas", "Gorilla", "Leo", "Loxodonta", "Panthera", "Python"]
30index = binary_search_recursive(species, "Leo")
31print(f"'Leo' at position: {index}") # 2
32
33index = binary_search_recursive(species, "Tyrannosaurus")
34print(f"'Tyrannosaurus' at position: {index}") # -1 (not found)Recursion with Multiple Calls
Sum of Digits
1def sum_digits(n):
2 """
3 Sum of digits of a number
4 Example: 12345 -> 1+2+3+4+5 = 15
5 """
6 if n < 10:
7 return n
8 return (n % 10) + sum_digits(n // 10)
9
10print(sum_digits(12345)) # 15
11print(sum_digits(999)) # 27Power
1def power(base, exp):
2 """
3 Power: base^exp
4 Example: power(2, 5) = 32
5 """
6 if exp == 0:
7 return 1
8 if exp == 1:
9 return base
10 return base * power(base, exp - 1)
11
12print(power(2, 5)) # 32
13print(power(3, 4)) # 81
14
15# Optimization - fast exponentiation (divide and conquer)
16def power_fast(base, exp):
17 """O(log n) instead of O(n)!"""
18 if exp == 0:
19 return 1
20 if exp == 1:
21 return base
22
23 # Divide the exponent in half
24 half = power_fast(base, exp // 2)
25
26 if exp % 2 == 0:
27 return half * half # even exponent
28 else:
29 return base * half * half # odd exponent
30
31print(power_fast(2, 10)) # 1024 (faster!)Recursion with Nested Lists
1def flatten_list(nested_list):
2 """
3 Flatten a nested list recursively
4 [[1, 2], [3, [4, 5]], 6] -> [1, 2, 3, 4, 5, 6]
5 """
6 result = []
7
8 for item in nested_list:
9 if isinstance(item, list):
10 # Recursively flatten the sublist
11 result.extend(flatten_list(item))
12 else:
13 result.append(item)
14
15 return result
16
17# Example
18nested = [[1, 2], [3, [4, 5]], 6, [7, [8, [9, 10]]]]
19flat = flatten_list(nested)
20print(flat) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
21
22# Safari example - nested teams
23teams = [
24 ["Darwin", "Alex"],
25 ["Maya", ["Sarah", "Tom"]],
26 "Chen",
27 ["Ahmed", ["Sofia", ["Lisa"]]]
28]
29all_members = flatten_list(teams)
30print(f"All team members: {all_members}")Safari Examples - Cave Exploration
1. Exploring Nested Caves
1def explore_caves(cave_system, depth=0):
2 """
3 Explore a nested cave system
4
5 cave_system: dict with key "name" and optionally "passages" (list of sub-caves)
6 """
7 indent = " " * depth
8 print(f"{indent}➡️ Entering: {cave_system['name']}")
9
10 # Base case - cave with no passages
11 if 'passages' not in cave_system or not cave_system['passages']:
12 print(f"{indent}🏁 Dead end! Returning...")
13 return
14
15 # Recursive case - explore passages
16 for passage in cave_system['passages']:
17 explore_caves(passage, depth + 1)
18
19 print(f"{indent}⬅️ Leaving: {cave_system['name']}")
20
21# Cave system
22jungle_caves = {
23 "name": "Main Cave",
24 "passages": [
25 {
26 "name": "Northern Tunnel",
27 "passages": [
28 {"name": "Crystal Chamber"},
29 {"name": "Waterfall"}
30 ]
31 },
32 {
33 "name": "Eastern Tunnel",
34 "passages": [
35 {
36 "name": "Deep Well",
37 "passages": [
38 {"name": "Underground Lake"}
39 ]
40 }
41 ]
42 },
43 {"name": "Western Tunnel"}
44 ]
45}
46
47explore_caves(jungle_caves)2. Counting Discoveries in Nested Structures
1def count_species(area):
2 """
3 Count species in nested areas
4
5 area: dict with 'species' (list) and optionally 'sub_areas' (list of areas)
6 """
7 # Count species in this area
8 count = len(area.get('species', []))
9
10 # Base case - no sub-areas
11 if 'sub_areas' not in area:
12 return count
13
14 # Recursive case - add from sub-areas
15 for sub_area in area['sub_areas']:
16 count += count_species(sub_area)
17
18 return count
19
20# Expedition area
21expedition_area = {
22 "name": "Main Jungle",
23 "species": ["Python regius", "Panthera leo"],
24 "sub_areas": [
25 {
26 "name": "Northern Forest",
27 "species": ["Gorilla gorilla", "Elephas maximus"],
28 "sub_areas": [
29 {
30 "name": "River",
31 "species": ["Crocodylus niloticus"]
32 }
33 ]
34 },
35 {
36 "name": "Savanna",
37 "species": ["Giraffa camelopardalis", "Loxodonta africana", "Panthera leo"]
38 }
39 ]
40}
41
42total = count_species(expedition_area)
43print(f"Total discovered: {total} species") # 8 species3. Finding a Path in a Maze
1def find_path_in_maze(maze, row, col, target, path=[]):
2 """
3 Find a path to the target in a maze recursively (Backtracking)
4
5 maze: 2D list ('.' = path, '#' = wall, 'T' = target)
6 row, col: current position
7 target: target position
8 path: current path
9 """
10 # Check if out of bounds or wall
11 if (row < 0 or row >= len(maze) or
12 col < 0 or col >= len(maze[0]) or
13 maze[row][col] == '#' or
14 maze[row][col] == 'V'): # 'V' = visited
15 return False
16
17 # Add to path
18 path.append((row, col))
19
20 # Base case - found the target!
21 if (row, col) == target:
22 return True
23
24 # Mark as visited
25 original = maze[row][col]
26 maze[row][col] = 'V'
27
28 # Try all 4 directions (up, down, left, right)
29 if (find_path_in_maze(maze, row - 1, col, target, path) or
30 find_path_in_maze(maze, row + 1, col, target, path) or
31 find_path_in_maze(maze, row, col - 1, target, path) or
32 find_path_in_maze(maze, row, col + 1, target, path)):
33 return True
34
35 # Backtrack - remove from path and restore
36 path.pop()
37 maze[row][col] = original
38 return False
39
40# Example maze
41maze = [
42 ['.', '.', '#', '.', '.'],
43 ['.', '#', '.', '#', '.'],
44 ['.', '.', '.', '.', '#'],
45 ['#', '#', '.', '#', '.'],
46 ['.', '.', '.', '.', 'T']
47]
48
49path = []
50start = (0, 0)
51target = (4, 4)
52
53if find_path_in_maze(maze, start[0], start[1], target, path):
54 print(f"Path found! Length: {len(path)}")
55 print(f"Path: {path}")
56else:
57 print("No path found!")Tail Recursion and Optimization
Tail recursion is recursion where the recursive call is the last operation in the function.
1# Not tail-recursive (multiplication after the call)
2def factorial_not_tail(n):
3 if n <= 1:
4 return 1
5 return n * factorial_not_tail(n - 1) # Operation after the call!
6
7# Tail-recursive (uses an accumulator)
8def factorial_tail(n, acc=1):
9 if n <= 1:
10 return acc
11 return factorial_tail(n - 1, n * acc) # The call is last!
12
13print(factorial_not_tail(5)) # 120
14print(factorial_tail(5)) # 120NOTE: Python does not optimize tail recursion automatically! But you can convert it to iteration.
Recursion vs Iteration - Performance
1import time
2import sys
3
4# Increase recursion limit (carefully!)
5sys.setrecursionlimit(10000)
6
7def compare_performance(n):
8 """Compare recursion vs iteration performance"""
9
10 # Recursion
11 start = time.time()
12 def factorial_recursive(x):
13 return 1 if x <= 1 else x * factorial_recursive(x - 1)
14 result_rec = factorial_recursive(n)
15 time_rec = time.time() - start
16
17 # Iteration
18 start = time.time()
19 def factorial_iterative(x):
20 result = 1
21 for i in range(1, x + 1):
22 result *= i
23 return result
24 result_iter = factorial_iterative(n)
25 time_iter = time.time() - start
26
27 print(f"n = {n}")
28 print(f"Recursion: {time_rec:.6f}s")
29 print(f"Iteration: {time_iter:.6f}s")
30 print(f"Iteration is {time_rec/time_iter:.1f}x faster\n")
31
32compare_performance(100)
33compare_performance(500)
34compare_performance(1000)
35
36# Typical results:
37# n = 100: Iteration ~2x faster
38# n = 500: Iteration ~3x faster
39# n = 1000: Iteration ~4x faster (and safer - smaller call stack)Practical Exercise
Create an "Expedition Analyzer":
- Count all species in a nested area structure
- Find the deepest nesting level
- Create a list of all area names (flatten the hierarchy)
- Calculate the average number of species per area
- Find the path to a specific area
Summary
In this lesson you learned:
- ✅ What recursion is (a function calling itself)
- ✅ Base case and recursive case
- ✅ How the call stack works
- ✅ Recursion vs iteration - when to use which
- ✅ Classic examples: factorial, Fibonacci, binary search
- ✅ Recursion with nested lists
- ✅ Backtracking (maze, paths)
- ✅ Tail recursion and optimization
- ✅ Practical Safari applications
Checkpoint
Before moving on:
- [ ] You understand what recursion is
- [ ] You can identify the base case and recursive case
- [ ] You understand the difference between recursion and iteration
- [ ] You can write a simple recursive function
- [ ] You understand the concept of the call stack
- [ ] You know when to use recursion and when to use iteration
- [ ] You know the limitations of recursion (stack overflow)
Golden rule: Recursion for naturally recursive problems (trees, graphs, divide-and-conquer), iteration for simple loops!
🎉 Congratulations! You've completed Module 2!
In this module you learned:
- ✅ Lists - the basic data structure
- ✅ Dictionaries - key-value pairs
- ✅ Comprehensions - elegant collection creation
- ✅ Algorithm complexity - Big O notation
- ✅ Sorting - different algorithms and applications
- ✅ Stacks and queues - LIFO and FIFO
- ✅ Recursion - functions calling themselves
What's next? In Module 3 Darwin will introduce you to Object-Oriented Programming - how to classify species using classes and objects! Get ready to learn OOP, inheritance, encapsulation, and much more! 🚀🐍