a way of breaking a problem down into smaller and smaller
pieces which eventually solve the problem
a way of repeating code (similar to a loop) so it is a control
structure
it's all of these
Calculating the Total of a List of Numbers
define the total of some numbers in a list as the total of (the
first element) and (the total of the rest of the list)
total of the whole list is list[0] + total (list minus the first
element)
reuse the definition but on a smaller argument
def total(list):
if len(list) == 1: # base case
answer = list[0]
elif len(list) == 0: # another base case
answer = 0
else:
answer = list[0] + total(list[1:]) # recursive part
return answer
The Three Laws of Recursion
must have a base case which is NOT recursive (at least one base case, can be more)
must have a recursive case which calls itself
the recursive case must move the problem towards the base case
the base case
can have more than one "if num == 0 or num == 1:"
sometimes the base case is just to NOT do anything
def fun(num):
if num > 0:
print(num)
fun(num-1)
the order of statements in a recursive function are even MORE important
than in other code
try reversing the two statements inside the if block above
safer to make sure the base case is tested for FIRST so that
you don't fall into the recursive case by accident
imagine the call stack when a recursive function is executing
gets taller as the function calls itself
gets shorter as the base cases execute and return values
an infinite loop in a recursive function will cause call
stack to run out of space (or Python has fixed limit of how tall the
stack can be)
a call stack is made up of the information about the function
call which is about to start = parameter values, place for the return value
to go when it's found