Calling Other Functions
Compare:
def hypotenuse(a, b):
return sqrt(sum_of_squares(a, b))
def sum_of_squares(x, y):
return square(x) + square(y)
def square(x): ?
return x * x a
Versus: b
def hypotenuse(a, b):
return sqrt((a*a) + (b*b))
The Call Stack
Michael Caine Just Ended An Eight Year Long Debate Over The Ending Of "Inception"
Stack
• First in last out order
First in Last Out
The Stack (or the Call Stack)
The Stack (or the Call Stack)
>>> p1(3)
Entering function p1
Entering function p2
Entering function p3
Line before return in p3
Line before return in p2
Line before return in p1
9
FILO!
Going in
Exiting a function
p3()
p2()
p1()
Parameters are LOCAL variables
Scope of x in
p1
Scope of x in
p2
Does not refer to
Scope of x in
p3
Practices (Convention)
• Global variables are VERY bad practices,
especially if modification is allowed
• 99% of time, global variables are used as
CONSTANTS
– Variables that every function could access
– But not expected to be modified
Convention:
Usually in all CAPs
Calling Other Functions Yourself?
Recursion
A Central Idea of CS
Some examples of recursion (inside and outside CS):
Garfield dreaming
recursively.
Sierpinksi triangle
Droste effect
Recursive tree
Recursion
• A function that calls itself
• And extremely powerful
technique
• Solve a big problem by solving
a smaller version of itself
– Mini-me
Factorial
• The factorial n! is defined by def factorial(n):
ans = 1
𝑛𝑛! = 1 × 2 × 3 × ⋯ × 𝑛𝑛 i = 1
while i <= n:
• Write a function for factorial? ans = ans * i
i = i + 1
print(ans)
>>> factorial(3)
6
>>> factorial(6)
720
>>>
Factorial
𝑛𝑛! = 1 × 2 × 3 × ⋯ × 𝑛𝑛
1 if 𝑛𝑛 = 0
𝑛𝑛! = �
𝑛𝑛 − 1 ! × 𝑛𝑛 otherwise
Factorial
def factorial(n):
ans = 1
i = 1
while i <= n:
ans = ans * i
i = i + 1
print(ans)
def factorialR(n):
if n == 1:
return 1
else:
return n * factorialR(n-1)
Recursion
• Rules of recursion Must have a terminal
condition
def factorialR(n):
if n == 1:
return 1
else:
return n * factorialR(n-1)
Must reduce the
size of the
problem for
every layer
Fibonacci Number
(Recursion)
Starting from 2
Rabbits
How many ways to arrange cars?
• Let’s say we have two types of vehicles, cars
and buses
• And each car can park into one parking space,
but a bus needs two consecutive ones
• If we have 1 parking space, I can only park a car
1 way
• But if there are 2 parking spaces, we can either
park a bus or two cars
2 ways
•
How many ways to arrange cars?
• So if we have 3 parking spaces, how many
different ways can we park cars and buses?
3 ways
How many ways to arrange cars?
• So if we have 4 parking spaces, how many
different ways can we park cars and buses?
5 ways
How many ways to arrange cars?
• 5 parking spaces?
• 6 parking spaces? #parking spaces #ways
0 1
1 1
2 2
3 3
4 5
5 8
6 13
• Can you figured out THE pattern?
– 1, 1, 2, 3, 5, 8, 13, …
– What is the next number?
How many ways to arrange cars?
• In general, if we have n parking spaces, how many ways
can we park the vehicles?
• You can think backward, the last parking space can be
either a car or a bus
?
• If it’s a car, there are n - 1 spaces left, you can have the
number of way for n - 1 spaces
– Otherwise, it’s the number of way for n - 2 spaces
• So
f (n) = f (n - 1) + f (n - 2) for f(0) = f(1) = 1
Fibonacci Numbers
• Fibonacci numbers are found in
nature (sea-shells, sunflowers, etc)
• http://www.maths.surrey.ac.uk/hos
ted-
sites/R.Knott/Fibonacci/fibnat.html
Challenge
• Write a fibonacci function that can compute
f(n) for n > 1000
Google about Recursion
• Try to search these in Google:
– Do a barrel roll
– Askew
– Anagram
– Google in 1998
– Zerg rush
• More in Google Easter Eggs
