Chapter 4: Recursion & Looping (continued)¶
The while Statement¶
Trivial Example: Countdown (revisited)¶
In [1]:
def countdown(n):
"""Print a countdown until the party starts.
Args:
n (int): seconds until the party begins; must be positive
"""
while n != 0:
print(n)
n -= 1
print("Happy new Year!")
In [2]:
countdown(3)
3 2 1 Happy new Year!
"Still involved" Example: Euclid's Algorithm 
(revisited)
In [3]:
def gcd(a, b):
"""Calculate the greatest common divisor of two numbers.
Args:
a (int): first number; must be positive
b (int): second number; must be positive
Returns:
gcd (int)
"""
while a != b:
if a > b:
a -= b
else:
b -= a
return a
In [4]:
gcd(12, 4)
Out[4]:
4
In [5]:
gcd(7, 7919)
Out[5]:
1
Efficiency of Algorithms (continued)¶
In [6]:
%%timeit -n 1 -r 1
gcd(112233445566778899, 987654321)
5.32 s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)
Infinite Loops¶
"Mystery" Example: Collatz Conjecture
Let's play the following game:
- Think of any positive integer $n$.
- If $n$ is even, the next $n$ is half the old $n$.
- If $n$ is odd, multiply the old $n$ by $3$ and add $1$ to obtain the next $n$.
- Repeat these steps until you reach $1$.
Do we always reach the final $1$?
In [7]:
def collatz(n):
"""Print a Collatz sequence in descending order.
Given a positive integer n, modify it according to these rules:
- if n is even, the next n is half the previous one
- if n is odd, the next n is 3 times the previous one plus 1
- if n is 1, stop the iteration
Args:
n (int): a positive number to start the Collatz sequence at
"""
while n != 1:
print(n, end=" ")
if n % 2 == 0:
n //= 2 # //= to preserve the int type
else:
n = 3 * n + 1
print(1)
In [8]:
collatz(100)
100 50 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
In [9]:
collatz(1000)
1000 500 250 125 376 188 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
In [10]:
collatz(10000)
10000 5000 2500 1250 625 1876 938 469 1408 704 352 176 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
The for Statement¶
In [12]:
elements = [0, 1, 2, 3, 4]
In [13]:
index = 0
while index < len(elements):
element = elements[index]
print(element, end=" ")
index += 1
del index
0 1 2 3 4
In [14]:
for element in elements:
print(element, end=" ")
0 1 2 3 4
In [15]:
for element in range(5):
print(element, end=" ")
0 1 2 3 4
In [16]:
type(range(5))
Out[16]:
range
In [17]:
for element in [1, 3, 5, 7, 9]:
print(element, end=" ")
1 3 5 7 9
In [18]:
for element in range(1, 10, 2):
print(element, end=" ")
1 3 5 7 9
Containers vs. Iterables¶
In [19]:
first_names = ["Achim", "Berthold", "Carl", "Diedrich", "Eckardt"]
In [20]:
"Achim" in first_names
Out[20]:
True
In [21]:
"Alexander" in first_names
Out[21]:
False
In [24]:
for name in first_names:
print(name, end=" ")
Achim Berthold Carl Diedrich Eckardt
In [25]:
for i, name in enumerate(first_names, start=1):
print(i, ">", name, end=" ")
1 > Achim 2 > Berthold 3 > Carl 4 > Diedrich 5 > Eckardt
"Hard at first Glance" Example: Fibonacci Numbers (revisited)
In [29]:
def fibonacci(i):
"""Calculate the ith Fibonacci number.
Args:
i (int): index of the Fibonacci number to calculate
Returns:
ith_fibonacci (int)
"""
a = 0
b = 1
print(a, b, sep=" ", end=" ") # added for didactical purposes
for _ in range(i - 1):
temp = a + b
a = b
b = temp
print(b, end=" ") # added for didactical purposes
return b
In [30]:
fibonacci(12) # = 13th number
0 1 1 2 3 5 8 13 21 34 55 89 144
Out[30]:
144
Efficiency of Algorithms (continued)¶
In [31]:
fibonacci(99) # = 100th number
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025 20365011074 32951280099 53316291173 86267571272 139583862445 225851433717 365435296162 591286729879 956722026041 1548008755920 2504730781961 4052739537881 6557470319842 10610209857723 17167680177565 27777890035288 44945570212853 72723460248141 117669030460994 190392490709135 308061521170129 498454011879264 806515533049393 1304969544928657 2111485077978050 3416454622906707 5527939700884757 8944394323791464 14472334024676221 23416728348467685 37889062373143906 61305790721611591 99194853094755497 160500643816367088 259695496911122585 420196140727489673 679891637638612258 1100087778366101931 1779979416004714189 2880067194370816120 4660046610375530309 7540113804746346429 12200160415121876738 19740274219868223167 31940434634990099905 51680708854858323072 83621143489848422977 135301852344706746049 218922995834555169026
Out[31]:
218922995834555169026
Easy Example: Factorial (revisited)
In [32]:
def factorial(n):
"""Calculate the factorial of a number.
Args:
n (int): number to calculate the factorial for, must be positive
Returns:
factorial (int)
"""
product = 1 # because 0! = 1
for i in range(1, n + 1):
product *= i
print(product, end=" ") # added for didactical purposes
return product
In [33]:
factorial(3)
1 2 6
Out[33]:
6