NB: Recursion

Programming for Data Science

What is Recursion?

Recursion in the context of programming occurs when a function calls to itsef.

This seems strange, since you’d think that to be called, a function must first be defined … And yet the definition contains a the function!

This is a bit like having a dictionary definition use the word it’s trying to define.

However, a function definition is not like a dictionary definition.

It does not define a thing. It defines a set of instructions.

So, in effect, when a function calls itself, the instruction is:

“Go back to the beginning of the code block with a new set of argument values.”

Each time the function goes back to the beginning, Python keeps track of the nested function calls in a call stack.

This will become clearer with examples.

A Formal Definition

In mathematics and computer science, a class of objects or methods exhibits recursive behavior when it can be defined by two properties:

A simple base case or condition: a terminating scenario that does not use recursion to produce an answer.
A recursive step: a set of rules that reduces all successive cases toward the base case.

Every recursive function must have a base condition that stops the recursion or else the function calls itself infinitely.

A Note of Caution

In practice, the Python interpreter limits the depths of recursion to help avoid infinite recursions, resulting in stack overflows.

When excessive memory consumption occurs on the call stack, it results in a stack overflow error.

Recursion is cool, but is expensive and complicated.

Recursive functions can usually be implemented by traditional loops.

Example: Computing Factorials

The factorial of a number \(n\) is the product of all the integers from \(1\) to \(n\).

For example, the factorial of \(5\) (denoted as \(5!\)) is \(1\times2\times3\times4\times5 = 120\).

Let’s implement this in code using a recursive function.

def factorial(x):
    "Finds the factorial of an integer using recursion"
    
    # Base condition
    if x == 1: 
        return 1

    # Recursive step
    else:
        return x * factorial(x - 1) # Self-reference

Note how x gets smaller in the recursive step until it meets the base condition.

n = 5
factorial(n)

The same thing can be done as a while loop:

def factorial_while(x):
    "Finds the factorial of an integer using a while loop"
    result = x
    while x > 1:
        x -= 1
        result *= x
    return result

factorial_while(n)

And as a for loop:

def factorial_for(x):
    "Finds the factorial of an integer using a for loop"
    result = 1
    for i in range(1, x+1):
        result *= i
    return result

factorial_for(n)

Example: The Fibonacci sequence

The Fibonacci sequence is defined by a series of numbers that equal the sum of the two previous numbers.

Mathematically, we define it as follows:

\(Fib(1) = 0\) (base case 1)
\(Fib(2) = 1\) (base case 2)

For all integers \(n > 2\), \(Fib(n) = Fib(n − 1) + Fib(n − 2)\)

For \(n = 8\) the sequence is \(0, 1, 1, 2, 3, 5, 8, 13\).

def fibonacci(n):
    "Compute a Fibonacci value using recursion"
    if n <= 0:
        print("Incorrect input. Value must be 1 or greater.")
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

Here get the F number for a given positive integer:

n = 8
fibonacci(n)

Here we compute the sequence itself:

print(*[fibonacci(i) for i in range(1, n + 1)])

0 1 1 2 3 5 8 13

As a for loop:

def fibber(n):
    """
    Computes a Fibonacci Sequence using a for loop. 
    Returns a string of the series.
    """
    F = [0,1] 
    for i in range(2, n):
        F.append(F[i-1] + F[i-2])
    print(*F)

fibber(n)

0 1 1 2 3 5 8 13

Note that here, we are letting the data structure do the work.

Aside: A General Sequence Function

Recursive functions are often used to produce mathematical sequences, but since they have limits on depth, they are of limited use for this purpose.

Here is a function that can combine many sequences using two sequence parameters: * The initial state of the sequence, represented as the list seq. * For example, in the Fibonacci sequence, seq is [0, 1] * The function to apply to the sequence at each iteration, represneted as a lambda function with the arguments x and i for the the sequence list seq and the iteration number respectively. * For example, in the Fibonacci sequence the kernel function is lambda x, i: x[i-1] + x[i-2]

def sequencer(n = 10, seq=[1, 1, 2], kernel=lambda x, i: x[i-1] + x[i-2]):
    """
    Computes a Sequence using a for loop. 
    
    n: an integer which must be > 3. Defaults to 10.
    seq: is a list in the initial state of the sequence. 
        Must have at least one value. Defaults to Fibonacci [1,1,2]
    kernel: the function applied to the series at each iteration. 
        x stands for the seq list, 
        i to the iteration number. 
        Defaults to lambda x, i: x[i-1] + x[i-2]
    
    Prints the series as an undelimited string.
    """
    
    for i in range(len(seq), n): 
        seq.append(kernel(seq, i))
        
    print(*seq)

The series of positive integers

n = 8

sequencer(n, [1], lambda x, i: x[i-1] + 1)

1 2 3 4 5 6 7 8

The series of even numbers

sequencer(n, [2], lambda x, i: x[i-1] + 2)

2 4 6 8 10 12 14 16

The series of odd numbers

sequencer(n, [1], lambda x, i: x[i-1] + 2)

1 3 5 7 9 11 13 15

The series of Fibonacci numbers

sequencer(n, [0,1], lambda x, i: x[i-1] + x[i-2])

0 1 1 2 3 5 8 13

The series of Squares

sequencer(n, [2], lambda x, i: x[i-1]**2)

2 4 16 256 65536 4294967296 18446744073709551616 340282366920938463463374607431768211456