Recursion Basics.pdf

4 Pages

Computer Science
Course Code
Fiona Bawl

This preview shows page 1. Sign up to view the full 4 pages of the document.
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
Unlock Document

Only page 1 are available for preview. Some parts have been intentionally blurred.

Unlock Document
You're Reading a Preview

Unlock to view full version

Unlock Document

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.