Study Guides (256,415)
CA (124,635)
UTM (5,120)
CSC (34)
CSC148H5 (6)

Recursion Basics.pdf

4 Pages
286 Views

Department
Computer Science
Course Code
CSC148H5
Professor
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 ints #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 0 # 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)

Loved by over 2.2 million students

Over 90% improved by at least one letter grade.

Leah — University of Toronto

OneClass has been such a huge help in my studies at UofT especially since I am a transfer student. OneClass is the study buddy I never had before and definitely gives me the extra push to get from a B to an A!

Leah — University of Toronto
Saarim — University of Michigan

Balancing social life With academics can be difficult, that is why I'm so glad that OneClass is out there where I can find the top notes for all of my classes. Now I can be the all-star student I want to be.

Saarim — University of Michigan
Jenna — University of Wisconsin

As a college student living on a college budget, I love how easy it is to earn gift cards just by submitting my notes.

Jenna — University of Wisconsin
Anne — University of California

OneClass has allowed me to catch up with my most difficult course! #lifesaver

Anne — University of California
Description
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


OR

Don't have an account?

Join OneClass

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

Sign up

Join to view


OR

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.


Submit