# 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,
• 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.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')``````