Understanding Recursion and Generators
Understanding Recursion and Generators
Recursion
Fibonacci number: 0, 1, 1, 2, 3, 5, 8, 13, 21,....
Consider computing the Fibonacci number of order $n$: $$ F_n := \begin{cases}
F_{n-1}+F_{n-2} & n>1 \kern1em \text{(recurrence)}\\ 1 & n=1 \kern1em \text{(base
case)}\\ 0 & n=0 \kern1em \text{(base case)}. \end{cases}$$ Fibonacci numbers have
practical applications in generating pseudorandom numbers.
Can we define the function by calling the function itself?
Recursion) is a function that calls itself (recurs).
To be more specific, recursion is a method of solving a problem where the solution
depends on solutions to smaller instances of the same problem
In [3]: %%optlite -r -h 450
def fibonacci(n):
if n > 1:
return fibonacci(n - 1) + fibonacci(n - 2) # recursion
elif n == 1:
return 1
else:
return 0
fibonacci(3)
Out[3]: 2
Exercise Write a function gcd that implements the Euclidean algorithm for the
greatest common divisor: $$\operatorname{gcd}(a,b)=\begin{cases}a & b=0\\
\operatorname{gcd}(b, a\operatorname{mod}b) & \text{otherwise} \end{cases}$$
In [5]: def gcd(a, b):
# YOUR CODE HERE
if b==0:
return a
else:
return gcd(b, a%b) #recursion: call itself but with different par
gcd(15, 35)
Out[5]: 5
fibonacci_iteration(3)
Out[6]: 2
The answer is NO
In [8]: %%optlite -r -h 550
#how can we exchange the value of two variables a and b?
#is the following code correct?
a=1
b=5
a=b
b=a
a is 5 b is 5
Out[8]: OPTWidget(value=None, height=550, script="#how can we exchange the value
of two variables a and b? \n#is the f…
c=a
a=b
b=c
a is 5 b is 1
Out[9]: OPTWidget(value=None, height=650, script="#the following is the correct
way to exchange two variables\n#we nee…
a is 5 b is 1
x is 6 y is 1 z is 5
Exercise
We can always convert a recursion to an iteration. Why?
{hint}
See the [recursion vs iteration]
([Link]
{admonition}
The step-by-step execution of the recursion is indeed how
python implements a recursion as an iteration.
gcd_iteration(3 * 5, 5 * 7)
Out[11]: 5
In [14]: n=30
time1=[Link]() #get the current system time
fibonacci_iteration(n)
time2=[Link]() #get the current system time
print('Running time of iteration:{:.5f} seconds'.format(time2-time1))
To see why recursion is slow, we will modify fibonacci to print each function call
as follows.
In [15]: #this function show how many functions are called in order to calculate f
def fibonacci(n):
'''Returns the Fibonacci number of order n.'''
print('fibonacci({!r})'.format(n)) #everytime, we print the funtion
return fibonacci(n - 1) + fibonacci(n - 2) if n > 1 else 1 if n == 1
fibonacci(5)
fibonacci(5)
fibonacci(4)
fibonacci(3)
fibonacci(2)
fibonacci(1)
fibonacci(0)
fibonacci(1)
fibonacci(2)
fibonacci(1)
fibonacci(0)
fibonacci(3)
fibonacci(2)
fibonacci(1)
fibonacci(0)
fibonacci(1)
Out[15]: 5
Global Variables
reference book) and Closures (chapter 8.1 in
Actually, we already introduced global variables and local variables in Lecture 4:
using functions. Now, we'll introduce more details.
Local variable vs Global variable
A local variable is a variable declared inside a function. It can be only accessed
inside a function.
def add_1():
#global x
x = 10 #this x is a local variable
return x
print(add_1())
print(x)
10
5
def add_1():
global x #if you want to use global variable x in a function, you mus
x= 10
return x
print(add_1())
print(x)
10
10
Then, the following code also uses global variable x in function add_1() , but
doesn't use global to declare it, why it can be executed without any error?
In [18]: x=5 #x is a global variable
def add_1():
#global x
y = x + 1
return y
print(add_1())
print(x)
6
5
This is because we don't change the value of global variable x , so we don't need to
declare it.
In [21]: x=5 #x is a global variable
def add_1():
# global x
x = x + 1 # error because we change the value of global variable x
return x
print(add_1())
print(x)
--------------------------------------------------------------------------
-
UnboundLocalError Traceback (most recent call las
t)
Cell In[21], line 8
5 x = x + 1 # error because we change the value of global variab
le x
6 return x
----> 8 print(add_1())
9 print(x)
Out[32]: In Python, when we try to modify a global variable within a function wit
hout declaring it as global, we get an UnboundLocalError because Python
treats the variable as local by default. When the assignment operation i
s encountered, Python looks for a local variable with that name, but sin
ce it hasn't been initialized yet, it raises an UnboundLocalError, indic
ating that the local variable is referenced before assignment. This erro
r occurs because Python's scoping rules dictate that a variable is consi
dered local to a function if it's assigned a value anywhere within that
function, even if the assignment happens after the variable is reference
d. Since the global variable hasn't been explicitly declared, Python doe
sn't look for it in the global scope, resulting in the UnboundLocalError
when trying to modify its value.
name collision
If a function defines a local variable with the same name as a global variable, the
global variable become inaccessible to code within the function. We say the local
variable hides the like-named global variable from code in the function’s body. ---
page 235 of reference book
In [22]: #my_name is a global variable
my_name='Global variable'
#in this function, my_name is a local variable, here the global variable
def print_name():
my_name='Local variable' #local variable will hide global variable i
print(my_name)
Local variable
Global variable
def print_msg(msg):
# This is the outer enclosing function
s1=msg #s1 is a nonlocal variable
def printer():
# This is the nested function
nonlocal s1 #we need to use nonlocal to declare s1 in the inner f
global s
s2=s1 #s2 is a local variable
print(s2)
print(s)
printer()
Hello
CS1302
inner()
outer()
inner()
outer()
Python Closures
In the example above, we have called the inner function inside the outer function. The
inner function becomes a closure when we return the inner function instead of calling
it.
What happens if we don't call the inner function?
Run the code below to see the result
In [26]: def outer():
x = 1 #this x is a nonlocal variable
def inner():
nonlocal x #if we want to change x's value in the inner function,
x=x+1
print(x)
#inner()
outer()
myFunction=print_msg("Hello")
myFunction()
del print_msg #even we delete print_msg, the value "Hello" is still reme
myFunction()
Hello
Hello
In [29]: str1="hello"
print(str1)
del str1
print(str1)
hello
--------------------------------------------------------------------------
-
NameError Traceback (most recent call las
t)
Cell In[29], line 5
2 print(str1)
4 del str1
----> 5 print(str1)
Here, the call to outer function returns the inner function. This then gets
assigned to ‘myFunction’. Now when we call myFunction, it prints ‘Hello’ (which
was earlier given as an argument to outer).
[Link] and [Link] 10/19
3/20/25, 8:33 PM Recursion and Generator
Even after ‘outer’ finishes its execution and all its variables go out of scope, the
value passed to its argument is still remembered.
This is the beauty of closures! We can access the values of a function that no
longer exists.
More information can be found here
Function as data
We can treat function as data (int, string etc).
so a function name can be used as parameter
we can also return a function
See example below
In [30]: #this example shows we can use funtion name as input parameters and retur
def add(x, y):
"""
Adds the parameters x and y and returns the result
"""
return x + y
"""
Tests the add, multiply, and evaluate functions
"""
print(add(2, 3))
print(multiply(2, 3))
print(evaluate(add, 2, 3))
print(evaluate(multiply, 2, 3))
5
6
5
6
Generator
We can use iteration/loop to generate a sequence of value. Another way to generate
a sequence of value one-by-one is to write a generator.
[Link] and [Link] 11/19
3/20/25, 8:33 PM Recursion and Generator
#another example
x=(i for i in range(5))
print(type(x))
<class 'generator'>
<class 'generator'>
<class 'generator'>
[0, 1, 2, 3, 4]
0 1 2 3 4
it accepts a generator object and returns the next value in the generator’s
sequence
we'll get an error if we ask the generator to provide a value after the final value in
its sequence
In [34]: x=(i for i in range(5)) #0 1 2 3 4
print(next(x)) #0
print(next(x)) #1
print(next(x)) #2
print(next(x)) #3
print(next(x)) #4
print(next(x)) #raise an error cause there's no next value
0
1
2
3
4
--------------------------------------------------------------------------
-
StopIteration Traceback (most recent call las
t)
Cell In[34], line 7
5 print(next(x)) #3
6 print(next(x)) #4
----> 7 print(next(x)) #raise an error cause there's no next value
StopIteration:
0
1
2
3
4
Is fibonacci_generator efficient?
No again due to redundant computations.
A better way to define the generator is to use the keyword yield :
In [37]: %%optlite -h 500
def fibonacci_sequence(Fn, Fn1, stop):
while Fn < stop:
yield Fn # return Fn and pause execution
Fn, Fn1 = Fn1, Fn1 + Fn
{important}
{important}
return vs yield
- `return` will return the data and terminate a function
immediately
In one paragraph, explain what is the difference between return and yield
Out[38]: The primary difference between `return` and `yield` in Python is the way
they handle the flow of a function's execution. When a function encounte
rs a `return` statement, it terminates the function's execution and send
s the result back to the caller, after which the function's local variab
les are destroyed. In contrast, when a function encounters a `yield` sta
tement, it pauses the function's execution, returns the yielded value to
the caller, but retains the function's local variables, allowing the fun
ction to resume execution from the point where it left off when called a
gain. This difference makes `yield` particularly useful for creating gen
erators, which can produce a sequence of values on-the-fly, without havi
ng to store them all in memory at once, whereas `return` is typically us
ed for functions that compute a single value or a collection of values a
nd return them all at once.
n += 1
print('This is printed second')
return n
n += 1
print('This is printed at last')
return n
n += 1
print('This is printed second')
yield n
n += 1
print('This is printed at last')
yield n
n += 1
print('This is printed second')
yield n
n += 1
print('This is printed at last')
yield n
#we can use next() to replace for loop to continue to the next yield expr
So far, a generator can only generate some data, can it receive data?
Yes, we can use send() function
send() function can send a value to a generator
The send() method returns the next value yielded by the generator ,
or raises StopIteration if the generator exits without yielding another value.
When send() is called to start the generator, it must be called with None as the
argument, because there is no yield expression that could receive the value.
In [42]: def my_gen():
n=1
n=n+1
received_value=yield n
print("I received the second number:", received_value)
n=n+1
received_value=yield n
print("I received the third number:", received_value)
a=my_gen()
generated_value=next(a)
print("I generate:", generated_value)
generated_value=[Link](100)
print("I generate:",generated_value)
generated_value=[Link](200)
print("I generate:",generated_value)
#this send() will cause error because there's no more yield expression
generated_value=[Link](300)
I generate: 1
I received the first number: 100
I generate: 2
I received the second number: 200
I generate: 3
I received the third number: 300
--------------------------------------------------------------------------
-
StopIteration Traceback (most recent call las
t)
Cell In[42], line 27
24 print("I generate:",generated_value)
26 #this send() will cause error because there's no more yield expres
sion
---> 27 generated_value=[Link](300)
StopIteration:
fibonacci_generator = fibonacci_sequence(0, 1, 5)
print(next(fibonacci_generator))
print(fibonacci_generator.send(2))
for fib in fibonacci_generator:
print(fib)
fibonacci_generator = fibonacci_sequence(0, 1, 5)
print(next(fibonacci_generator))
print(fibonacci_generator.send(2))
for fib in fibonacci_generator:
print(fib)
0
2
2
4
Example:
```python
def infinite_sequence():
num = 0
while True:
yield num
num += 1
seq = infinite_sequence()
print(next(seq)) # prints 0
print(next(seq)) # prints 1
print(next(seq)) # prints 2
```
**Send in Python**
Example:
```python
def echo():
while True:
received = yield
print("Received:", received)
echo_gen = echo()
next(echo_gen) # advances the generator to the first yield
echo_gen.send("Hello") # prints "Received: Hello"
echo_gen.send("World") # prints "Received: World"
```
Note that `send()` can only be used after the generator has been advance
d to the first `yield` statement using `next()`. If `send()` is called b
efore `next()`, a `TypeError` is raised.