Dr. Cho’s Website
Course Materials

Recursion and exceptions in Python

Institute for Environmental and Spatial Analysis...University of North Georgia

1   Recursion

1.1   How it works

We are revisiting recursion (Factorial from the pre-assessment).

Recursion uses the growing call stack:

1. Global execution context
2. Call recursive
3. Call recursive
4. ...
5. Return \$\leftarrow\$ Base case
6. 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]
tail = []
for i in range(0, len(array)):
if i == pivot_index:
continue
elif array[i] <= pivot:
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.

Built-in exceptions

2.2   An example: Division by zero

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.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')