Our recursion adventures:

#  Fibonacci sequence calculations

# n:      0  1  2  3  4  5  6  7  8  9
# fib(n): 0  1  1  2  3  5  8  13 21 34

# A non-recursive function for calculating the nth Fibonacci number:
def fib(n):
    if n < 2:
        return n
    prev = 0
    curr = 1
    for i in range(2,n+1):
        new_curr = prev + curr
        prev = curr
        curr = new_curr
    return curr

# Calculating the ratios of pairs of Fibonacci numbers -- like fib(6)/fib(5)
def CalcFibRatios(low,high):
    for i in range(low,high+1):
        print(timeit(i)/timeit(i-1))
        
# The recursive function for Fibonacci
def fib_r(n):
    if n < 2:
        return n
    return fib_r(n-1) + fib_r(n-2)

# Timing how long it takes to calculate fib_r(n)
def timeit(n):
    import time
    start = time.time()
    fib_r(n)
    end = time.time()
    return end - start

def fib_r2_helper(prev, curr, pos, target):
    if pos == target:
        return curr
    her_pos = pos + 1
    her_curr = curr + prev
    her_prev = curr
    her_target = target
    return fib_r2_helper(her_prev, her_curr, her_pos, her_target)

def fib_r2(n):
    if n == 0:
        return 0
    return fib_r2_helper(0, 1, 1, n)
   
==========================================================================
Recursive definitions beyond simple computer algorithms

These are examples of Backus-Naur Form: https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form

For the abbreviations below:
NF means Noun-phrase
ADJ means adjective
DS means Digit-string
PDIGIT means Positive-digit
NNN means Non-negative-number

Here's the recursive definition of a Noun-phrase:
NF := NOUN | ADJ NF

Here's the definition of a non-negative number (we're excluding numbers that look like 00065, for instance):
DIGIT := 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
DS := DIGIT | DIGIT DS
PDIGIT := 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
NNN := DIGIT | PDIGIT DS

For the definition of INTEGER below, why isn't it just "INTEGER := NNN | - NNN" ?
INTEGER := NNN | - PDIGIT | - PDIGIT DS