Recursion and exceptions in Python
1 Recursion
1.1 How it works
We are revisiting recursion (Factorial from the pre-assessment).
Recursion uses the growing call stack:
- Global execution context
- Call recursive
- Call recursive
- ...
- Return $\leftarrow$ Base case
- Start unwinding the call stack all the way up
Which means... an infinite never stopping recursion can quickly
- Eat up CPU resources,
- Fill your memory, and
- Crash your computer if your host program is not smart enough to kill it!
1.2 Want to crash your machine?
Try this at home ;-) (DISCLAIMER: Do it at your own risk!)
def recursive(x)
return recursive(x-1)
recursive(1)
Stack overflow protection by Python
import sys
print(sys.getrecursionlimit())
sys.setrecursionlimit(2000)
1.3 Append an element
Recursive calls of a non-recursive function
def append_element(element, list):
return list + [element]
append_element(1,
append_element(2,
append_element(3,
append_element(4,
append_element(5, [])))))
1.4 Summation
def sum(n):
if n == 0:
return 0
else:
return n + sum(n-1)
print(sum(10))
1.5 Factorial
def fact(n):
if n == 0:
return 1
else:
return n * fact(n-1)
print(fact(5))
1.6 Quick sort
Quick sort is a divide and conquer algorithm, which is naturally recursive.
def quicksort(array):
if len(array) <= 1:
return array
pivot_index = int(len(array)/2)
pivot = array[pivot_index]
head = []
tail = []
for i in range(0, len(array)):
if i == pivot_index:
continue
elif array[i] <= pivot:
head.append(array[i])
else:
tail.append(array[i])
return quicksort(head) + [pivot] + quicksort(tail)
import random
arr = random.sample(range(100), 100)
sorted_arr = quicksort(arr)
print('Random: ', arr)
print('Sorted: ', sorted_arr)
1.7 Fibonacci number
Each number is the sum of the two preceding numbers. \[ F_n = F_{n-1} + F_{n-2} \]
The very first two numbers are 0 and 1. \[ F_0 = 0, F_1 = 1 \]
def fibonacci(n):
if n == 0 or n == 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
for i in range(0, 20):
print(fibonacci(i))
2 Exceptions
2.1 What are exceptions?
Code may be syntactically correct.
However, run-time errors can still occur anytime.
When these happen, a Python program just crashes without proper handling of those run-time errors.
2.2 An example: Division by zero
Let’s start with this.
x = 10 / 0
A “ZeroDivisionError: division by zero” exception is thrown.
2.3 Handling exceptions
Let’s handle the previous exception instead of letting the program crash.
try:
x = 10 / 0
except:
print("Oops! Something went wrong...")
But what is wrong? We know the exception name: ZeroDivisionError
.
try:
x = 10 / 0
except ZeroDivisionError:
print('Oops! Tried to divide by zero')
2.4 Print built-in exception messages
try:
x = 10 / 0
except ZeroDivisionError as err:
print(f'Oops! {err}')
try:
print(y)
except NameError as err:
print(f'lassOops! {err}')
2.5 Handling multiple exceptions
try:
x = 10 / 0
print(y)
except NameError as err:
print(f'Oops! {err}')
except ZeroDivisionError as err:
print(f'Oops! {err}')
2.6 Raising exceptions
We can throw exceptions ourselves.
try:
x = 0
if x == 0:
raise ValueError('x cannot be 0')
except ValueError as err:
print(f'Oops! {err}')
Do you just want to know that an exception occurred without handling it? Re-raise the same exception
try:
x = 0
if x == 0:
raise ValueError('x cannot be 0')
except ValueError as err:
print(f'Oops! {err}')
raise # make the program stop here
2.7 User-defined exceptions
We can derive our own exceptions from the Exception
class.
class MyError(Exception):
def __init__(self, message):
self.message = message
try:
raise MyError('Ah!')
except MyError as err:
print(err)
2.8 Derived exceptions
Derived exceptions are not compatible with base exceptions.
class FirstError(Exception): pass
class SecondError(FirstError): pass
class ThirdError(SecondError): pass
for error in (FirstError, SecondError, ThirdError):
try:
raise error()
except ThirdError: # derived from SecondError; cannot handle SecondError
print("ThirdError")
except SecondError: # derived from FirstError; cannot handle FirstError
print("SecondError")
except FirstError: # derived from Exception; cannot handle Exception
print("FirstError")
2.9 Base exceptions
Base exceptions are compatible with derived exceptions.
class FirstError(Exception): pass
class SecondError(FirstError): pass
class ThirdError(SecondError): pass
for error in (FirstError, SecondError, ThirdError):
try:
raise error()
except FirstError: # derived from Exception; Exception can handle this
print("FirstError")
except SecondError: # derived from FirstError; FirstError can handle this
print("SecondError")
except ThirdError: # derived from SecondError; SecondError can handle this
print("ThirdError")
2.10 Finally
A finally
clause is always executed.
try:
x = 10 / 0
except ZeroDivisionError as err:
print(f'Oops! {err}')
finally:
print('Done')
try:
x = 10 / 1
except ZeroDivisionError as err:
print(f'Oops! {err}')
finally:
print('Done')