Recursion and exceptions in Python

Dr. Huidae Cho
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]
    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.

Built-in exceptions

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