# CHAPTER 12: RECURSION ## 12.1 WRITING RECURSIVE ALGORITHMS ### 12.1.1 Essential Components 1. **Base Case:** Condition that stops recursion 2. **Recursive Case:** Function calls itself with modified parameters ### 12.1.2 Examples **Sum of Numbers:**
<PYTHON>
def sum(n):
if n == 1:
return 1
else:
return n + sum(n-1)
**Counting Characters in String:**
<PYTHON>
def count(char, string):
if string == "":
return 0
elif string\[0\] == char:
return 1 + count(char, string\[1:\])
else:
return count(char, string\[1:\])
**Reverse String:**
<PYTHON>
def reverse(string):
if len(string) <= 1:
return string
else:
return reverse(string\[1:\]) + string\[0\]
### 12.1.3 Tracing Recursion
<TEXT>
sum(4)
= 4 + sum(3)
= 4 + (3 + sum(2))
= 4 + (3 + (2 + sum(1)))
= 4 + (3 + (2 + 1))
= 4 + (3 + 3)
= 4 + 6
= 10