CODE/NOTE TAKEN FROM DISCUSSION BOARD WHICH WAS REDISTRIBUTED
Tracing Recursion
- Trace the simplest case
- Then trace the next most complex case (plug in known results)
Code
def rec_max (lst):
'''(list of int, can be nested) -> int
Return max number in possible nested list of numbers.
>>> rec_max([17,21, 0])
21
>>> rec_max ([17,[21,24],0])
24
'''
nums = []
#never to make a recursive call ? every elemnt has to be an int(no nesting)
for element in lst:
if isinstance(element, int): #always will be true ( no recursion )
nums.append(element)
else:
nums.append(rec_max(element))
return max(nums)
Tracing Recursion that you Should do( refer to the code above)
Base case for this function: list of int#no nesting
rec_max([21,24]) is 24
rec_max([17,[21,24],0]) #base case for function = [21, 24]
rec_max([17,[21,24],0]
nums= []
first element = 17 #goes into sublist
next thing in the list is [21, 24# but already know that its 24 ( no recursive calls)
last element of the list is int # so append into num
therefore num = [17, 24, 0]
Once the for loop is done ( it returns the max of the sublist you make)
max(nuns) is 24, so 24 is returned
Solve simplest problems first then use these to solve the more complex solutions.
(this is how you TRACE but computer goes top down, biggest more complex cases
first then does the simplest ones) Computer Tracing Recursion
- python keeps currently copies of the function
- keeps a stack of currently active function calls
- when a new function is added it puts it on top of the old one
- when it hits a base case it can then terminate
- easier to see with the example
Example Tracing Recursion ( the way the Computer does it)
Call 1:
rec_max([17,[21,24],0]
# run function until hits recursive call (solves it then goes back to finish the rest)
num = [] # set numb to empty
element = 17
is the if statement true ? # Yes so 17 gets appended to num
num = [17] # now looks like this
now element = [21, 24] # the sublist, since it goes through the for loop
if statement isn’t true but else is (stuck cause now you need to make a recursive call)
Call 2: #once you know answer c

More
Less