CHAPTER 12: RECURSION

12.1 WRITING RECURSIVE ALGORITHMS

12.1.1 Essential Components

Base Case: Condition that stops recursion
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