Recursion
Announcements
Recursive Functions
Recursive Functions
Definition: A function is called recursive if the body of that function calls itself, either directly or indirectly
Implication: Executing the body of a recursive function may require applying that function
Drawing Hands, by M. C. Escher (lithograph, 1948)
!4
Digit Sums
•If a number a is divisible by 9, then sum_digits(a) is also divisible by 9 •Useful for typo detection!
2+0+1+9 = 12
The Bank of 61A
1234 5678 9098 7658 OSKI THE BEAR
A checksum digit is a
function of all the other
digits; It can be
computed to detect typos
• Credit cards actually use the Luhn algorithm, which we’ll implement after sum_digits
!5
The Problem Within the Problem
n, last = split(n)
digit_sum = digit_sum + last
return digit_sum
def sum_digits_rec(n, digit_sum):
if n == 0:
return digit_sum
else:
Updates via assignment become…
n, last = split(n)
return sum_digits_rec(n, digit_sum + last)
…arguments to a recursive call
!18