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!