The PYTimes Congrats, Pats! Homework #1 Due Fri.,

The PYTimes Congrats, Pats! Homework #1 Due Fri.,

The PYTimes Congrats, Pats! Homework #1 Due Fri., 2/13 Homework #0 Due Fri., 2/6 1-2) Python challenges 0) Reading/response 3-5) Picobot challenges 1) Lab: data 6) Reading response Prof Alienated!? Todays whether: if, elif, or else!

Composite sketch of one of the attackers drawn from three-eyewitness accounts 2) Lab: data + functions 3) Putting the fun into functions! Alien Attack? Picobot programmer Z. Dodds was subject of a bizarre attack yesterday by three-eyed aliens. The trinocular terrors, it seems, were conducting experiments that would help them understand how humans think. It seems the aliens used a shrinking ray, which let them enter the programmers head in order to see what was happening. A witness reports deeply disappointed voices emanating from within. see three-eyed alien attack, p. 42 sible for

s o p 's t i f i slation: n a r t , too? c S i C t a r o m

f o s t p u a A s... perh e g a u g n a l human uses a "shell" language Computer command-line

% cd Desktop % ls or dir % python % python hw1pr1.py Python command-line just about all we'll do runs the Python language >>> 6*7 >>> s = 'harvey mudd college' >>> len(s) >>> s.upper()

this feels like CS5's primary topic! Picobot!? Jack Ma's Picobot rules Data, data everywhere Data 1 Zettabyte 1.8 ZB 8.0 ZB 800 EB Data produced each year 161 EB 1 Exabyte

5 EB 100-years of HD video + audio 1 Petabyte 1 Petabyte == 1000 TB 1 TB = 1000 GB 60 PB Human brain's capacity 2002 logarithmic scale Data, data everywhere 14 PB 2006

2009 2011 2015 References (2015) 8 ZB: http://www.emc.com/collateral/analyst-reports/idc-extracting-value-from-chaos-ar.pdf (2002) 5 EB: http://www2.sims.berkeley.edu/research/projects/how-much-info-2003/execsum.htm (2011) 1.8 ZB: http://www.emc.com/leadership/programs/digital-universe.htm (2009) 800 EB: http://www.emc.com/collateral/analyst-reports/idc-digital-universe-are-you-ready.pdf (life in video) 60 PB: in 4320p resolution, extrapolated from 16MB for 1:21 of 640x480 video (w/sound) almost certainly a gross overestimate, as sleep can be compressed significantly! (2006) 161 EB: http://www.emc.com/collateral/analyst-reports/expanding-digital-idc-white-paper.pdf (brain) 14 PB: http://www.quora.com/Neuroscience-1/How-much-data-can-the-human-brain-store Big Data?

'debt' more-than-average searches for debt: sell fewer-than-average searches for debt: buy 'fun' 'water' not quite sure where we are right now? The Technology Hype Cycle If you torture the data enough, it will confess. - R. Coates, statistician Data's elevation? wisdom

G.G.M, et al. G. Garcia Marquez knowledge Google's users information Google data Python's data types Name Example What is it? float 3.14

values with a fractional part long 10**100 integers > 2147483647 int 42 integers <= 2147483647 bool True False the results from a comparison: "Boolean value"

Hey - someone can't spelle ! George Boole ==, !=, <, >, <=, >= Datatypes ~ genes What will these results be? Dominant float 1.0 / 5 long 10**100 - 10**100 int bool

Recessive 1 / 5 41 + True Operate! higher precedence ( ) ** * % / + > == < = O-per-ate! higher precedence (

) ** * % / + > == < = Python operators parens ( power negate times, mod, divide add, subtract compare assign higher precedence ) **

* % / + > == < = It's not worth remembering all these %+/* things! Id recommend parentheses over precedence. % the mod operator 7 % 3 9 % 3 8 % 3 16 % 7 x%y returns the remainder when x is divided by y x%2 == 0 For what values of x are these True?

x%2 == 1 x%4 == 0 What happens on these years? x%4 == 3 the "equals" operators = != == This is true but what is it saying!? the "equals" operators = != == SET equals isn't equal to TEST equals I want === !

Try it! Run these lines name or names x = 41 y = x + 1 z = x + y What are x, y, and z at this time? Then run this how = works x y

z a = 11/2 b = a%3 c = b** a+b *a x = x + y What are x, y, and z at this time? x Extra! y z What are the values of a, b, and c after these lines run? Inside the machine

What's happening in python: x = 41 y = x + 1 What is happening behind the scenes: Computation Data Storage 41 42 name: x type: int LOC: 312 name: y type: int LOC: 324 memory location 312

memory location 324 variables ~ boxes id, del Memory! Random Access Memory 41 42 83 105 name: x type: int LOC: 312 name: y

type: int LOC: 324 name: z type: int LOC: 336 name: a type: int LOC: 348 a big list of boxes, each with a name, type, location, and value 512 MB of memory Wow! Who knew they make memory out of wicker? on or off bit = 1 "bucket" of charge byte = 8 bits

Are numbers enough for everything? Yes and no You need lists of numbers, as well! and strings - lists of characters - too. Both of these are Python sequences string functions str(42) len('42') 'XL' + 'II' 'VI' * 7 returns returns returns returns converts input to a string '42' returns the strings length

2 concatenates strings 'XLII' 'VIVIVIVIVIVIVI' repeats strings composing strings using + and * string functions str(42) len('42') 'XL' + 'II' 'VI' * 7 returns returns returns returns Given these strings What are converts input to a string

'42' returns the strings length 2 concatenates strings 'XLII' 'VIVIVIVIVIVIVI' repeats strings s1 = 'ha' s2 = 't' s1 + s2 2*s1 + s2 + 2*(s1+s2) What did you say!?! Data ~ dig in! s = 'harvey' 0 1 2 3 4 5 s[2] is

'r' s[2:4] is 'rv' s[::-1] is 'yevrah' index indexing slicing Indexing uses [ ]

s = 'harvey mudd college' 0 1 2 3 4 5 6 7 8 9 index s[0] is s[6] is s[ ] is 10 11 12

13 14 15 Read as "s-of-zero" or "s-zero" 'e' 16 17 18 In a negative mood ? Python's there for you ! Negative indices 0 1 2 3 4 5 6 7 8 9

10 11 12 13 14 15 16 17 18 s = 'harvey mudd college' -19 -17

-18 -15 -16 -13 -14 -11 -12 -9 -10 -7 -8 -5 -6 -3 -4

-1 -2 Negative indices count backwards from the end! s[-1] is s[-2] is s[-0] is Slicing s = 'harvey mudd college' 0 1 2 3 4 5 6 7 8 9 s[ : ]

10 11 12 13 14 15 16 17 18 slices the string, returning a substring What's going on here?

s[0:6] is 'harvey' s[12:18] is 'colleg' s[17:] is 'ge' s[:] is 'harvey mudd college' Slicing s = 'harvey mudd college' 0 1 2 3 4 5 6 7 8 9 s[ : ] first index is the first character 10 11 12 13 14

15 16 17 18 slices the string, returning a substring second index is ONE AFTER the last character a missing index means that end of the string s[0:6] is 'harvey' s[12:18] is 'colleg' s[17:] is 'ge' s[:] is 'harvey mudd college' Slicing

s = 'harvey mudd college' 0 1 2 3 4 5 6 7 8 9 What are these slices? and these? s[15:-1] is s[:2] is is is 10

11 12 13 14 15 'mud' 'e' 16 17 18 Don't wor'e'Be hap'e' ! SkipSlicing

the third index is the stride length s[ : : ] default is +1 s = 'harvey mudd college' 0 1 2 3 4 5 6 7 8 9 s[0:8:2] is s[17:12:-1] is is s[1::6] 10

11 12 13 14 15 16 17 18 'hre ' 'doe' G. Garcia Marquez

is I love this one. Lists ~ collections of any data L = [ 3.14, [2,40], 'third', 42 ] Commas separate elements. Square brackets tell python you want a list. Lists ~ collections of any data L = [ 3.14, [2,40], 'third', 42 ] len(L) L[0] length indexing could return a different type From L how

could you get 'hi' L[0:1] slicing always returns the same type, and always returns a substructure! Try it! pi = [3,1,4,1,5,9] L = [ 'pi', "isn't", [4,2] ] M = 'You need parentheses for24 chemistry !' 0 4 8

12 16 20 28 32 Part 1 ( ) Part 2 6 What is len(pi) What is len(L) We What is L[0] 3 'pi'

What is L[0:1] What is len(L[1]) What is L[0][1] What is pi[2:4] What slice of M is 'try'? What slice of pi is [3,1,4] What slice of pi is [3,4,5] Extra! Mind Muddlers These two are different, too These two are different! pi[:3]

What is 'i' is 'shoe'? M[9:15] What is M[::5] What are pi[0]*(pi[1] + pi[2]) and pi[0]*(pi[1:2] + pi[2:3]) ? pi = [3,1,4,1,5,9] L = [ 'pi', "isn't", [4,2] ] M = 'You need parentheses for24 chemistry !' 0 4 8 12 16

20 28 32 Part 1 ( ) Part 2 6 What is len(pi) What is len(L) We What is L[0] 3 What is L[0:1] What is len(L[1])

What is pi[2:4] element sublist What is L[0][1] [4,1] What slice of M is 'try'? is 'shoe'? M[31:34] What slice of pi is [3,1,4] pi[:3] What is What slice of pi is [3,4,5]

pi[::2] What is M[::5] Extra! Mind Muddlers 'pi' ['pi'] M[9:15] 'parent' What are pi[0]*(pi[1] + pi[2]) and pi[0]*(pi[1:2] + pi[2:3]) ? 15 [1,4,1,4,1,4] pi = [3,1,4,1,5,9] L = [ 'pi', "isn't", [4,2] ] M = 'You need

parentheses for24 chemistry !' 0 4 8 12 16 20 28 32 Part 1 ( ) Part 2 6 What is len(pi) What is len(L) We

What is L[0] 3 What is len(L[1]) What is pi[2:4] What is L[0:1] 5 [4,1] What is L[0][1] element sublist 'i' What slice of M is 'try'? M[31:34]

What slice of pi is [3,1,4] pi[:3] What is What slice of pi is [3,4,5] pi[::2] What is M[::5] Extra! Mind Muddlers 'pi' ['pi'] M[9:15] is 'shoe'? M[30:16:-4]

'parent' 'Yeah cs!' What are pi[0]*(pi[1] + pi[2]) and pi[0]*(pi[1:2] + pi[2:3]) ? 15 [1,4,1,4,1,4] Python slices - it dices... ( data, at least ) but wait, there's more! Functioning in Python # my own function! def dbl( x ): """ returns double its input, x """ return 2x This doesn't look quite right

Functioning in Python # my own function! comment for other coders def dbl( x ): """ returns double its input, x """ return 2*x Python's keywords documentation string for all users Some of Python's baggage Functioning in Python def undo(s): """ this "undoes" its input, s """ return 'de' + s

>>> undo('caf') 'decaf' >>> undo(undo('caf')) strings, lists, numbers all data are fair game Computation's Dual Identity Computation Data Storage 41 42 name: x type: int LOC: 300 name: y type: int LOC: 304

memory location 300 memory location 304 variables ~ boxes But what does all this stuff look like ? Las e m i tt Functioning across disciplines procedure def g(x): return x**100 structure g(x) = x

100 CS's googolizer Math's googolizer defined by what it does + how efficiently it works defined by what it is Giving names to data def flipside(s): """ flipside(s): swaps s's sides! input s: a string """ This idea is the key to x = len(s)/2 your happiness! return s[x:] + s[:x] Use variables!

Hey - I'm happy about this, too! def flipside(s): x = len(s)/2 return s[x:] + s[:x] def flipside(s): return s[len(s)/2:] + s[:len(s)/2] Avoid this approach Why would computers "prefer" the top version, too? Challenge How functions work -4 What is demo(-4) ? def demo(x): return x + f(x) def f(x):

return 11*g(x) + g(x/2) def g(x): return -1 * x I might have a guess How functions work def demo(x): return x + f(x) def f(x): return 11*g(x) + g(x/2) demo stack frame x = -4 return -4 + f(-4) def g(x): return -1 * x Hey! This must be a stack-frame frame!

>>> demo(-4) ? How functions work def demo(x): return x + f(x) def f(x): return 11*g(x) + g(x/2) demo stack frame x = -4 return -4 + f(-4) f def g(x): return -1 * x >>> demo(-4) ? stack frame x = -4 return 11*g(x) + g(x/2)

How functions work def demo(x): return x + f(x) def f(x): return 11*g(x) + g(x/2) demo stack frame x = -4 return -4 + f(-4) f def g(x): return -1 * x >>> demo(-4) ? stack frame x = -4 return 11*g(x) + g(x/2)

These are distinct memory locations both holding x's. How functions work def demo(x): return x + f(x) def f(x): return 11*g(x) + g(x/2) demo stack frame x = -4 return -4 + f(-4) f g >>> demo(-4) ? stack frame x = -4 return 11*g(-4) + g(-4/2)

def g(x): return -1 * x x = -4 return -1.0 * x stack frame How functions work def demo(x): return x + f(x) def f(x): return 11*g(x) + g(x/2) demo stack frame x = -4 return -4 + f(-4) f x = -4 return 11* 4

def g(x): return -1 * x g >>> demo(-4) ? x = -4 return stack frame + g(-4/2) done! -1 * -4 4 How functions work def demo(x): return x + f(x) def f(x): return 11*g(x) + g(x/2)

demo stack frame x = -4 return -4 + f(-4) f def g(x): return -1 * x >>> demo(-4) ? x = -4 return 11* 4 stack frame + g(-4/2) the "return value" How functions work def demo(x): return x + f(x)

def f(x): return 11*g(x) + g(x/2) demo stack frame x = -4 return -4 + f(-4) f x = -4 return 11* 4 def g(x): return -1 * x g >>> demo(-4) ? x = -2 return -1 * -2

stack frame + g(-4/2) 2 These are distinct memory locations both holding x's and now they also have different values!! How functions work def demo(x): return x + f(x) def f(x): return 11*g(x) + g(x/2) demo stack frame x = -4 return -4 + f(-4) f def g(x): return -1 * x

>>> demo(-4) ? x = -4 return 11* 4 stack frame + 2 the "return value" How functions work def demo(x): return x + f(x) def f(x): return 11*g(x) + g(x/2) demo stack frame x = -4 return -4 + f(-4) f

def g(x): return -1 * x >>> demo(-4) ? x = -4 return 11* 4 + 2 46 How functions work def demo(x): return x + f(x) def f(x): return 11*g(x) + g(x/2) demo x = -4 return -4 + def g(x):

return -1 * x >>> demo(-4) 42 42 stack frame 46 Douglas Adams's 42 Those zero-eyed aliens are a bit much answer: 42 question: unknown Function stacking def demo(x): return x + f(x) def f(x):

return 11*g(x) + g(x/2) demo stack x = -4 return -4 + f(-4) f "The stack" is a memory area that the stack x = -4 return 11* 4 def g(x): return -1 * x g x = -2

return frame + g(-4/2) -1 * -2 2 (1) keeps separate variables for each function call (2) remembers where to send results back to return > print def dbl(x): """ dbls x? """ return 2*x

def dblPR(x): """ dbls x? """ print 2*x >>> ans = dbl(21) >>> ans = dblPR(21) return > print def dbl(x): """ dbls x? """ return 2*x def dblPR(x): """ dbls x? """ print 2*x >>> ans = dbl(21)

>>> ans = dblPR(21) print just prints stuff to the screen... return yields the function call's value which the shell then prints! Challenge! 3 def myst(x): """ _myst_ery fun' """ print "x is", x if x <= 1: print "Done! Returning 1" return 1 else:

print "Calling myst(", x-1, ")" old_result = myst( x-1 ) new_result = x * old_result print "Returning", new_result return new_result What eight lines does myst(3) print? Challenge! What eight lines does myst(3) print? 3 def myst(x): """ _myst_ery fun' """ print "x is", x if x <= 1: print "Done! Returning 1" return 1 else:

print "Calling myst(", x-1, ")" old_result = myst( x-1 ) new_result = x * old_result print "Returning", new_result return new_result x is 3 Calling myst( 2 ) x is 2 Calling myst( 1 ) x is 1 Done! Returning 1 Returning 2 Returning 6 returns 6 Function design Thinking sequentially factorial 5! =

120 5! = 5*4*3*2*1 N! = N * (N-1) * (N-2) * * 3 * 2 * 1 Thinking sequentially factorial 5! = 120

5! = 5*4*3*2*1 N! = bit late r (March a nd b N * (N-1) * (N-2) * * e 3 *y 2o * 1n d) Thinking recursively factorial

5! = 120 5! = 5*4*3*2*1 5! = N! = N! =

Recursion == self-reference! N * (N-1) * (N-2) * * 3 * 2 * 1 Warning: this is legal! def fac(N): return N * fac(N-1) I wonder how this code will STACK up!? legal != recommended def fac(N): return N * fac(N-1) The calls to fac will never stop: there's no BASE CASE! Make sure you have a base case, then worry about the recursion... Thinking recursively

def fac(N): if N <= 1: return 1 Base case "How could I use the factorial of Ask yourself: anything smaller than N?" Then do! Thinking recursively def fac(N): if N <= 1: return 1 Base case else: return N*fac(N-1) Human: Base case and 1 step Recursive

case (shorter) Computer: Everything else Thinking recursively def fac(N): if N <= 1: return 1 Base case else: rest = fac(N-1) return rest * N Human: Base case and 1 step Recursive case (clearer, for some) Computer: Everything else

def fac(N): Behind the curtain if N <= 1: return 1 else: return N * fac(N-1) fac(5) def fac(N): Behind the curtain if N <= 1: return 1 else: return N * fac(N-1) fac(5)

5 * fac(4) def fac(N): Behind the curtain if N <= 1: return 1 else: return N * fac(N-1) fac(5) 5 * fac(4) 5 * 4 * fac(3) Operation waiting def fac(N): Behind the curtain

if N <= 1: return 1 else: return N * fac(N-1) fac(5) 5 * fac(4) 5 * 4 * fac(3) 5 * 4 * 3 * fac(2) More operations waiting def fac(N): Behind the curtain if N <= 1: return 1 else: return N * fac(N-1)

fac(5) 5 * fac(4) 5 * 4 * fac(3) 5 * 4 * 3 * fac(2) 5 * 4 * 3 * 2 * fac(1) def fac(N): Behind the curtain if N <= 1: return 1 else: return N * fac(N-1) "The Stack" Stack frames hold all of the individual calls to fac

fac(5) N=5 5 * fac(4) N=4 5 * 4 * fac(3) N=3 5 * 4 * 3 * fac(2) N=2 5 * 4 * 3 * 2 * fac(1) N=1 5 * 4 * 3 * 2 * 1

N's are t n e r e f 5 dif mory e m n i living def fac(N): Behind the curtain if N <= 1: return 1

else: return N * fac(N-1) fac(5) 5 * fac(4) 5 * 4 * fac(3) 5 * 4 * 3 * fac(2) 5 * 4 * 3 * 2 * 1 def fac(N): Behind the curtain if N <= 1: return 1 else: return N * fac(N-1) fac(5) 5 * fac(4)

5 * 4 * fac(3) 5 * 4 * 3 * 2 def fac(N): Behind the curtain if N <= 1: return 1 else: return N * fac(N-1) fac(5) 5 * fac(4) 5 * 4 * 6 def fac(N):

Behind the curtain if N <= 1: return 1 else: return N * fac(N-1) fac(5) 5 * 24 def fac(N): Behind the curtain if N <= 1: return 1 else: return N * fac(N-1)

fac(5) Result: 120 show Look familiar? R P facW 0 x*** -> N 0 Recursive step 0 N*** -> X 1 Base case Thinking recursively

What will print when facWPR(5) is called? Let recursion do the work for you. Exploit self-similarity Produce short, elegant code Less work ! You handle the base case the easiest case! def fac(N): if N <= 1: Recursion does almost all of return 1 the rest of the problem! else: You specify one step at the end rest = fac(N-1) return rest * N

But you do need to do one step yourself def fac(N): if N <= 1: return 1 else: returnThisfac(N) not w will ork ! Recursion's advantage: As a hat, I'm recursive, too! It handles arbitrary structural depth all at once! The dizzying dangers of having no base case! Recursive design (1) Program the base case.

!? y s a e fun! (2) Find the self-similarity. cool! (3) Do one step! ing c i l s and g n

i x e ind (4) Delegate the rest to recursion Aha! One step? is easy to do with Python s = 'aliens' How do we get at the initial character of s? How do we get at ALL THE REST of s? s[0] s[ ] 'liens' L = [ 42, 21 ] How do we get at the initial element of L?

How do we get at ALL THE REST of L? L[0] L[ ] [ 21 ] def mylen(s): Picture it! """ returns the number of characters in s input: s, a string """ NOT a space this is no characters at all. This is the empty string and it has length of 0! s = '' mylen('') 0 starts with a vowel count that vowel and

delegate the rest to recursion s = 'hi' mylen('hi') 1+mylen( ) wow! s = 'recursion' mylen('recursion') 1+mylen( ) def mylen(s): Picture it! """ returns the number of

characters in s input: s, a string """ NOT a space this is no characters at all. This is the empty string and it has length of 0! Base case test s = '' mylen('') if 0 p == 0 : return Base case

starts with a vowel count that vowel and delegate the rest to recursion s = 'hi' mylen('hi') 1+mylen( ) else: return wow! Recursive case s = 'recursion' mylen('recursion') 1+mylen( )

Try it! complete ! def mylen(s): """ input: any string, s output: the number of characters in s """ if s == '': return 0 else: return 1 + mylen(s[1:]) There's not much len left here! Behind the curtain: how recursion works... mylen('cs5') 1 + mylen('s5') 1 + 1 + mylen('5') 1 + 1 + 1 + mylen('')

1 + 1 + 1 + 0 def mylen(s): if s == '': return 0 else: return 1 + mylen(s[1:]) Visualizing http://www.pythontutor.com/visualize.html Picture it! def mymax(L): """ returns the max of a nonempty list of elements, L """ one-element list is the smallest list that HAS a max L = [42] mymax([42])

42 first element is less than the second element! L = [1,4,42] mymax([1,4,42]) mymax( ) first element is bigger than the second element! L = [4,1,3,42,7] mymax([4,1,3,42,7]) mymax( ) Picture it!

def mymax(L): """ returns the max of a nonempty list of elements, L """ Base case test one-element list is the smallest list that HAS a max if len(L) == 1: L = [42] mymax([42]) return 42 Base case elif

first element is less than the second element! L = [1,4,42] mymax([1,4,42]) : test of first vs. second elements return mymax([4,42]) Recursive case #1 else: return first element is bigger than the second element!

Recursive case #1 L = [4,1,3,42,7] mymax([4,1,3,42,7]) mymax([4,3,42,7]) Try it! base case drop 1st drop 2nd def mymax(L): if len(L) == 1: return L[0] elif L[0] < L[1]: return mymax( L[1:] ) else: return mymax( L[0:1]+L[2:] ) mymax( [1,4,3,42,-100,7] ) mymax( [4,3,42,-100,7] )

mymax( [4,42,-100,7] ) mymax( [42,-100,7] ) mymax( [42,7] ) mymax( [42] ) 42 def power(b,p): Picture it! 0 2 == """ returns b to the p power Use recursion, not ** Inputs: int b, int p: the base and the power """ 1

power(2,0) -> 1 5 2 == 4 2* 2 4 power(2,5) -> 2*2 Do you see the call to power!? p 2

== 2* 2 What should this be? power(2,p) -> 2*power(,) power(b,p) -> def power(b,p): Picture it! 0 2 == """ returns b to the p power Use recursion, not ** Inputs: int b, int p: the base and the power

""" 1 Base case test if power(2,0) -> 1 p == 0 : return Base case 5 2 ==

4 2* 2 4 power(2,5) -> 2*2 Do you see the call to power!? else: p 2 == 2* 2 What should this be?

return Recursive case power(2,p) -> 2*power(,) power(b,p) -> Want more power? Handle negative p values w/elif. E.g., power(5,-1) == 0.2 Try it! power( 2, 5 ) 2* power( 2, 4 ) 2* 2* power( 2, 3 ) 2* 2* 2* power( 2, 2 ) 2* 2* 2* 2* power( 2, 1 ) 2* 2* 2* 2* 2* power( 2, 0 ) 2* 2* 2* 2* 2* 1 32 Picture it!

'' def sajak(s): """ returns the number of vowels in the input string, s """ NOT a space this is no characters at all. This is the empty string and it has 0 vowels! sajak('') 0 starts with a vowel count that vowel and delegate the rest to recursion 'okay' sajak('okay') 1+sajak( )

starts with a consonant so skip it and delegate the rest! 'what' sajak('what') 0+sajak( ) Picture it! '' def sajak(s): """ returns the number of vowels in the input string, s """ Base case test NOT a space this is no characters at all. This is the empty string and it has 0 vowels! sajak('')

s == '': if 0 return starts with a vowel count that vowel and delegate the rest to recursion 'okay' elif sajak('okay') 1+sajak( ) else:

starts with a consonant so skip it and delegate the rest! 'what' sajak('what') return return 0+sajak( ) Want more Pat? What 7-letter English word w maximizes sajak(w) ? Try it! sajak( 'eerier' ) 1+ sajak( 'erier' ) 1+ 1+ sajak( 'rier' )

1+ 1+ 0+ sajak( 'ier' ) 1+ 1+ 0+ 1+ sajak( 'er' ) 1+ 1+ 0+ 1+ 1+ sajak( 'r' ) 1+ 1+ 0+ 1+ 1+ 0+ sajak( '' ) 1+ 1+ 0+ 1+ 1+ 0+ 0 4 def power(b,p): """ inputs: base b and power p (an int) implements: b**p """ if p == 0: return 1.0 elif p < 0: return ____________________ else: return b * power(b,p-1) Recursion is power! sajak(s):

Base case? Rec. step? wels # of vo in s D When there are no letters, there are ZERO vowels Look at the initial character. if s[0] is NOT a vowel, the answer is sajak( s[1:] ) if s[0] is a vowel, the answer is 1 + sajak( s[1:] ) E S I

G N def sajak(s): if s == '': return 0 Is s[0] a vowel? elif s[0]=='a' or s[0]=='e' or but how to check for vowels? Python is in I guess Python's the in thing >>> 'i' in 'team' False

>>> 'cs' in 'physics' True >>> 'i' in 'alien' True >>> 42 in [41,42,43] True >>> 3*'i' in 'alien' False >>> 42 in [[42], '42'] False let's input 'eerier' for s def sajak(s): if len(s) == 0: return 0 elif s[0] return sajak(s[1:]) Base Case

if s[0] IS a vowel, the answer is 1 + the # of vowels in the rest of s in 'aeiou': 1 + Recursive Cases else: return sajak(s[1:]) 0 + if s[0] is NOT a vowel, the answer is just the number of vowels in the rest of s The key to understanding recursion is, first, to understand recursion. - a former CS 5 student It's the eeriest!

h t i w k c u l d Goo 1 # k r o w e m Ho tutors @ LAC all week! def power(b,p):

""" returns b to the p power Use recursion, not ** Inputs: int b, int p: the base and the power """ Base case test if p == 0 : Picture it! 0 2 == 1 power(2,0) -> 1

return Base case 5 2 == 4 2* 2 4 power(2,5) -> 2*2 Do you see the call to power!? else: return

Recursive case Try it! Want more power? Handle negative values of p in an elif. For example, power(5,-1) == 0.2 p 2 == 2* 2 power(2,p) -> 2*power() power(2,5) == 32.0 Try it! sajak('wheel of fortune') == 6

What about y? You decide in general: def power(b,p): """ returns b to the p power Use recursion, not ** Inputs: int b, int p: the base and the power """ p == 0 if : Base case test return elif

def sajak(s): """ returns the number of vowels in the input string, s """ s == '': if return elif return else: else: return return Want more power? Handle negative values of p in an elif. For example, power(5,-1) == 0.2 Want more Pat?

What 7-letter English word w maximizes sajak(w) ? Base case test def mylen(s): Picture it! """ returns the number of characters in s input: s, a string """ NOT a space this is no characters at all. This is the empty string and it has length of 0! Base case test s = '' mylen('')

if 0 p == 0 : return Base case starts with a vowel count that vowel and delegate the rest to recursion s = 'hi' mylen('hi') 1+mylen( ) else:

return wow! Recursive case s = 'recursion' mylen('recursion') 1+mylen( ) [1,4,3,42,-100,7] Design #2 def mymax(L): """ input: a NONEMPTY list, L output: L's maximum element """ if len(L)==1 : base case test!

return elif : another case return else: return Design #2 def mymax(L): """ input: a NONEMPTY list, L output: L's maximum element """ if len(L) == 1: return L[0] elif L[0] < L[1]: return mymax( L[1:] ) else: return mymax( L[0:1] + L[2:] ) Hey - do I get a

slice?! Computation's Dual Identity Computation Data Storage 41 42 name: x type: int LOC: 300 name: y type: int LOC: 304 memory location 300 memory location 304 variables ~ boxes

But what does all this stuff look like ? me i t t Las Giving names to data def flipside(s): """ flipside(s): swaps s's sides! input s: a string """ x = len(s)/2 This idea is the key to return s[x:] + s[:x] your happiness! Use variables! Hey - I'm happy

about this, too! def flipside(s): x = len(s)/2 return s[x:] + s[:x] def flipside(s): return s[len(s)/2:] + s[:len(s)/2] Avoid this approach Why would computers "prefer" the top version, too? (1) function definition Test! def flipside(s): """ flipside(s): swaps s's sides! input s: a string """ x = len(s)/2 return s[x:] + s[:x] #

# Tests! # print "flipside('carpets') print "flipside('carpets') print "flipside('carpets') print "flipside('carpets') print "flipside('carpets') (2) function tests ~", ~", ~", ~", ~", flipside('carpets') flipside('carpets') flipside('carpets') flipside('carpets') flipside('carpets') !

s i h t e k i l t s e t t ' n o d t bu We provide these tests (for now) control-b in Sublime

Using variables This program uses variables constantly! def convertFromSeconds(s): # total seconds """ convertFromSeconds(s): Converts an integer # of seconds into a list of [days, hours, minutes, seconds] input s: an int """ seconds = s % 60 # leftover seconds m = s / 60 # total minutes minutes = m % 60 # leftover minutes h = m / 60 # total hours hours = h % 24 # leftover hours

days = h / 24 # total days return [days, hours, minutes, seconds] How functions look e m a n def convertFromSeconds(s): input(s) # total seconds """ convertFromSectons(s): Converts an integer # of seconds into a list of [days, hours, minutes, seconds] input s: an int """ seconds = s % 60 # leftover seconds m = (s / 60) # total minutes

minutes = m % 60 # leftover minutes h = m / 60 # total hours hours = h % 24 # leftover hours comments days = h / 24 # total days these are mostly return [days, hours, minutes, seconds] docstring code block return statement optional in CS 5 Computation's Dual Identity accessed through functions

Computation t c n u F Data Storage 41 42 name: x type: int LOC: 300 name: y type: int LOC: 304 memory location 300

memory location 304 ! s n io variables ~ boxes It's no coincidence this starts with fun! Functioning across disciplines procedure def g(x): return x**100 structure g(x) = x 100 CS's googolizer

Math's googolizer defined by what it does + how efficiently it works defined by what it is Quiz First and last name(s): -4 What is demo(-4) ? def demo(x): return x + f(x) def f(x): return 11*g(x) + g(x/2) def g(x): return -1 * x

I might have a guess How functions work How functions work def demo(x): return x + f(x) def f(x): return 11*g(x) + g(x/2) demo stack frame x = -4 return -4 + f(-4) def g(x): return -1 * x Hey! This must be a stack-frame frame! >>> demo(-4) ?

How functions work def demo(x): return x + f(x) def f(x): return 11*g(x) + g(x/2) demo stack frame x = -4 return -4 + f(-4) f def g(x): return -1 * x >>> demo(-4) ? stack frame x = -4 return 11*g(x) + g(x/2) How functions work

def demo(x): return x + f(x) def f(x): return 11*g(x) + g(x/2) demo stack frame x = -4 return -4 + f(-4) f def g(x): return -1 * x >>> demo(-4) ? stack frame x = -4 return 11*g(x) + g(x/2) These are distinct memory locations both holding x's.

How functions work def demo(x): return x + f(x) def f(x): return 11*g(x) + g(x/2) demo stack frame x = -4 return -4 + f(-4) f g >>> demo(-4) ? stack frame x = -4 return 11*g(-4) + g(-4/2) def g(x):

return -1 * x x = -4 return -1.0 * x stack frame How functions work def demo(x): return x + f(x) def f(x): return 11*g(x) + g(x/2) demo stack frame x = -4 return -4 + f(-4) f x = -4 return 11* 4 def g(x): return -1 * x

g >>> demo(-4) ? x = -4 return stack frame + g(-4/2) done! -1 * -4 4 How functions work def demo(x): return x + f(x) def f(x): return 11*g(x) + g(x/2) demo

stack frame x = -4 return -4 + f(-4) f def g(x): return -1 * x >>> demo(-4) ? x = -4 return 11* 4 stack frame + g(-4/2) the "return value" How functions work def demo(x): return x + f(x) def f(x): return 11*g(x) + g(x/2)

demo stack frame x = -4 return -4 + f(-4) f x = -4 return 11* 4 def g(x): return -1 * x g >>> demo(-4) ? x = -2 return -1 * -2 stack frame + g(-4/2)

2 These are distinct memory locations both holding x's and now they also have different values!! How functions work def demo(x): return x + f(x) def f(x): return 11*g(x) + g(x/2) demo stack frame x = -4 return -4 + f(-4) f def g(x): return -1 * x >>> demo(-4) ?

x = -4 return 11* 4 stack frame + 2 the "return value" How functions work def demo(x): return x + f(x) def f(x): return 11*g(x) + g(x/2) demo stack frame x = -4 return -4 + f(-4) f def g(x): return -1 * x

>>> demo(-4) ? x = -4 return 11* 4 + 2 46 How functions work def demo(x): return x + f(x) def f(x): return 11*g(x) + g(x/2) demo x = -4 return -4 + def g(x): return -1 * x

>>> demo(-4) 42 42 stack frame 46 Function stacking def demo(x): return x + f(x) def f(x): return 11*g(x) + g(x/2) demo stack frame x = -4 return -4 + f(-4) f "The stack" is a memory area that

the stack x = -4 return 11* 4 def g(x): return -1 * x g x = -2 return + g(-4/2) -1 * -2 2 (1) keeps separate variables for each function call (2) remembers where to send results back to

return def dbl(x): """ dbls x? """ return 2*x >>> ans = dbl(21) > print def dblPR(x): """ dbls x? """ print 2*x >>> ans = dblPR(21) return def dbl(x): """ dbls x? """ return 2*x >>> ans = dbl(21) print >

print def dblPR(x): """ dbls x? """ print 2*x >>> ans = dblPR(21) just prints stuff to the screen... return yields the function call's value which the shell then prints! Function design Thinking sequentially factorial 5! =

120 5! = 5*4*3*2*1 N! = N * (N-1) * (N-2) * * 3 * 2 * 1 Thinking sequentially factorial 5! = 120 5!

= 5*4*3*2*1 N! = N * (N-1) * (N-2) * * 3 * 2 * 1 Mar ch + beyo nd Thinking recursively factorial 5! = 120

5! = 5*4*3*2*1 5! = N! = N! = Recursion == self-reference! N * (N-1) * (N-2) * * 3 * 2 * 1

Warning: this is legal! def fac(N): return N * fac(N-1) I wonder how this code will STACK up!? legal != recommended def fac(N): return N * fac(N-1) The calls to fac will never stop: there's no BASE CASE! Make sure you have a base case, then worry about the recursion... This runs ~ but does not help! def fac(N): return fac(N) Roadsigns and recursion

examples of self-fulfilling danger Recursion's advantage: As a hat, I'm recursive, too! It handles arbitrary structural depth all at once! The dizzying dangers of having no base case! Thinking recursively def fac(N): if N <= 1: return 1 Base case Thinking recursively def fac(N): if N <= 1: return 1

Ask yourself: Base case "How could I use the factorial of anything smaller than N?" Then do! Thinking recursively def fac(N): if N <= 1: return 1 Base case else: return N*fac(N-1) Human: Base case and 1 step Recursive case (shorter)

Computer: Everything else Thinking recursively def fac(N): if N <= 1: return 1 Base case else: rest = fac(N-1) return rest * N Human: Base case and 1 step Recursive case (clearer, for some) Computer: Everything else def fac(N):

Behind the curtain if N <= 1: return 1 else: return N * fac(N-1) fac(5) def fac(N): Behind the curtain if N <= 1: return 1 else: return N * fac(N-1) fac(5) 5 * fac(4)

def fac(N): Behind the curtain if N <= 1: return 1 else: return N * fac(N-1) fac(5) 5 * fac(4) 5 * 4 * fac(3) Operation waiting def fac(N): Behind the curtain

if N <= 1: return 1 else: return N * fac(N-1) fac(5) 5 * fac(4) 5 * 4 * fac(3) 5 * 4 * More operations waiting 3 * fac(2) def fac(N): Behind the curtain

if N <= 1: return 1 else: return N * fac(N-1) fac(5) 5 * fac(4) 5 * 4 * fac(3) 5 * 4 * 3 * fac(2) 5 * 4 * 3 * 2 * fac(1) def fac(N): Behind the curtain

if N <= 1: return 1 else: return N * fac(N-1) "The Stack" fac(5) N=5 5 * fac(4) N=4 5 * 4 * fac(3) 5 * 4 * Stack frames hold all of the

individual calls to fac N=3 3 * fac(2) 5 * 4 * 3 * 5 * 4 * 3 * 2 * N=2 2 * fac(1) 1 N=1 N's are t n e r e f

5 dif mory e m n i living def fac(N): Behind the curtain if N <= 1: return 1 else: return N * fac(N-1) fac(5) 5 * fac(4) 5 * 4 * fac(3)

5 * 4 * 3 * fac(2) 5 * 4 * 3 * 2 * 1 def fac(N): Behind the curtain if N <= 1: return 1 else: return N * fac(N-1) fac(5) 5 * fac(4)

5 * 4 * fac(3) 5 * 4 * 3 * 2 def fac(N): Behind the curtain if N <= 1: return 1 else: return N * fac(N-1) fac(5) 5 * fac(4) 5 *

4 * 6 def fac(N): Behind the curtain if N <= 1: return 1 else: return N * fac(N-1) fac(5) 5 * 24 def fac(N): Behind the

curtain if N <= 1: return 1 else: return N * fac(N-1) fac(5) Result: 120 show Look familiar? R P facW 0 x*** -> N 0

Recursive step 0 N*** -> X 1 Base case Thinking recursively What will print when facWPR(5) is called? Let recursion do the work for you. Exploit self-similarity Produce short, elegant code Less work ! You handle the base case the easiest case! def fac(N): if N <= 1: Recursion does almost all of

return 1 the rest of the problem! else: You specify one step at the end rest = fac(N-1) return rest * N But you do need to do one step yourself def fac(N): if N <= 1: return 1 else: returnThisfac(N) not w will ork ! Recursion's challenge? You need to see BOTH the self-similar pieces AND the whole thing simultaneously!

Nature prefers recursion, too! Are these rules for real? Yes... and no. Dragon's-blood Tree There still has to be a base case or else! Recursive design (1) Program the base case. (2) Find the self-similarity. (3) Do one step! ea fun! sy!?

cool! icing l s d g an n i x e ind (4) Delegate the rest to recursion Aha! One step? is easy to do with Python s = 'aliens' How do we get at the initial character of s?

How do we get at ALL THE REST of s? s[0] s[ ] 'liens' L = [ 42, 21 ] How do we get at the initial element of L? How do we get at ALL THE REST of L? L[0] L[ ] [ 21 ] Recursive design #1 'cs5' def mylen(s): """ input: any string, s output: the number of characters in s """ if :

base case test! else: return return Ask yourself: "How could I make use of the length of something smaller than s?" Then do! complete def mylen(s): """ input: any string, s output: the number of characters in s """ if s == '': return 0 else: return 1 + mylen(s[1:]) There's not much len left here!

Behind the curtain: how recursion works... mylen('cs5') 1 + mylen('s5') 1 + 1 + mylen('5') 1 + 1 + 1 + mylen('') 1 + 1 + 1 + 0 def mylen(s): if s == '': return 0 else: return 1 + mylen(s[1:]) Looking behind the curtain http://www.pythontutor.com/visualize.html [1,4,3,42,-100,7] Design #2

def mymax(L): """ input: a NONEMPTY list, L output: L's maximum element """ if : len(L)==1 elifbase case test! return another case return else: return : Design #2 def mymax(L): """ input: a NONEMPTY list, L output: L's maximum element """

if len(L) == 1: return L[0] elif L[0] < L[1]: return mymax( L[1:] ) else: return mymax( L[0:1] + L[2:] ) Hey - do I get a slice?! base case drop 1st drop 2nd def mymax(L): if len(L) == 1: return L[0] elif L[0] < L[1]: return mymax( L[1:] ) else: return mymax( L[0:1]+L[2:] ) mymax( [1,4,3,42,-100,7] )

mymax( [4,3,42,-100,7] ) mymax( [4,42,-100,7] ) mymax( [42,-100,7] ) mymax( [42,7] ) mymax( [42] ) 42 power(2,5) == 32.0 Try it! sajak('wheel of fortune') == 6 What about y? You decide in general: def power(b,p): """ returns b to the p power Use recursion, not ** Inputs: int b, int p: the base and the power """

p == 0 if : Base case test return elif def sajak(s): """ returns the number of vowels in the input string, s """ if s == '': return elif

return else: else: return return Want more power? Handle negative values of p in an elif. For example, power(5,-1) == 0.2 Want more Pat? What 7-letter English word w maximizes sajak(w) ? Base case test power( 2, 5 ) 2* power( 2, 4 ) 2* 2* power( 2, 3 ) 2* 2* 2* power( 2, 2 )

2* 2* 2* 2* power( 2, 1 ) 2* 2* 2* 2* 2* power( 2, 0 ) 2* 2* 2* 2* 2* 1 32 sajak( 'eerier' ) 1+ sajak( 'erier' ) 1+ 1+ sajak( 'rier' ) 1+ 1+ 0+ sajak( 'ier' ) 1+ 1+ 0+ 1+ sajak( 'er' ) 1+ 1+ 0+ 1+ 1+ sajak( 'r' ) 1+ 1+ 0+ 1+ 1+ 0+ sajak( '' ) 1+ 1+ 0+ 1+ 1+ 0+ 0 4 def power(b,p): """ inputs: base b and power p (an int) implements: b**p """ if p == 0:

return 1.0 elif p < 0: return ____________________ else: return b * power(b,p-1) Recursion is power! sajak(s): Base case? Rec. step? wels # of vo in s D When there are no letters, there are ZERO vowels

Look at the initial character. if s[0] is NOT a vowel, the answer is sajak( s[1:] ) if s[0] is a vowel, the answer is 1 + sajak( s[1:] ) E S I G N def sajak(s): if s == '': return 0 Is s[0] a vowel? elif s[0]=='a' or s[0]=='e' or

but how to check for vowels? Python is in I guess Python's the in thing >>> 'i' in 'team' False >>> 'cs' in 'physics' True >>> 'i' in 'alien' True >>> 42 in [41,42,43] True >>> 3*'i' in 'alien' False >>> 42 in [[42], '42'] False

let's input 'eerier' for s def sajak(s): if len(s) == 0: return 0 elif s[0] return sajak(s[1:]) Base Case if s[0] IS a vowel, the answer is 1 + the # of vowels in the rest of s in 'aeiou': 1 + Recursive Cases else: return

sajak(s[1:]) 0 + if s[0] is NOT a vowel, the answer is just the number of vowels in the rest of s The key to understanding recursion is, first, to understand recursion. - a former CS 5 student It's the eeriest! h t i w k c u l d Goo 1

# k r o w e m Ho tutors @ LAC W/Th/F/Sa/Su Recursion's challenge? You need to see BOTH the self-similar pieces AND the whole thing simultaneously! Nature prefers recursion, too! Are these rules for real? Yes... and no. Dragon's-blood Tree There still has to be a base case

or else!

Recently Viewed Presentations

  • Jugular Jugular Venous Venous Pressure Pressure Its easier

    Jugular Jugular Venous Venous Pressure Pressure Its easier

    Level of sternal angle is about 5 cm above the level of mid right atrium IN ANY POSITION. JVP measured in ANY position in which top of the column is seen easily. Usually JVP is less than 8 cm water...
  • U.S. History Custom Assessment

    U.S. History Custom Assessment

    Thinking Critically: An illustration communicates meaning without the use of words or speech. The artist of this cartoon is trying to teach us something about the concept of "Imperialism."Translate the meaning of this cartoon by constructing a single-sentence definition of....
  • CS 3501 - Chapter 2 Dr. Clincy Professor

    CS 3501 - Chapter 2 Dr. Clincy Professor

    The normalized product requires an exponent of 2210 = 101102. Floating-point overflow and underflow can cause programs to crash. Overflow occurs when there is no room to store the high-order bits resulting from a calculation. Underflow occurs when a value...
  • LET&#x27;S REVIEW. - Monroe Township School District

    LET'S REVIEW. - Monroe Township School District

    A NEW SIGNPOST. Today, we are learning a new signpost called Words of the Wiser. Turn and Talk: What might Words of the Wiser be, and what might it look like in our reading?
  • Key Principles for Interpreting the Holy Scriptures (Biblical

    Key Principles for Interpreting the Holy Scriptures (Biblical

    Luke 24:27 "And beginning with Moses and all the Prophets, he interpreted to them in all the Scriptures the things concerning himself." (ESV) καὶ ἀρξάμενος ἀπὸ Μωϋσέως καὶ ἀπὸ πάντων τῶν προφητῶν . διερμήνευσεν
  • EECS 252 Graduate Computer Architecture Lec 8 - ILP in loops

    EECS 252 Graduate Computer Architecture Lec 8 - ILP in loops

    Times New Roman Arial Helvetica Comic Sans MS Courier New Times Symbol Wingdings CS252-template Microsoft Excel Worksheet Microsoft Excel Chart EECS 252 Graduate Computer Architecture Lec 8 - ILP in loops Review: Dynamic hardware techniques for out-of-order execution Review: Scoreboard...
  • La Gloire de mon pere

    La Gloire de mon pere

    Après avoir joué, Marcel voit que l'homme le plait à sa tante. En retournant à la maison, elle lui dit que c'est le propriétaire du parc, mais que c'est « un secret. » Six mois plus tard, le bonhomme annonce...
  • Untitled Presentation - VACLAV

    Untitled Presentation - VACLAV

    The Fix by award-winning Bloomberg journalists Liam Vaughan and Gavin Finch, is the inside story of the Libor scandal, told through the journey of the man at the centre of it: a young, scruffy, socially awkward misfit from England whose...