Recursion examples in Python

"To iterate is human to recurse is divine"

- unknown programmer

In mathematics, the function is how we turn one thing into another thing. More essentially than that, we define functions to "map" one thing to another thing.  One of the more surprising features of functions is they can create other functions as an output - including themselves. This is the essential nature of recursion.

For example. If I want a function that returns the sum of (1 + 2 + 3 + ... n) numbers, I can define it as follows:

SumOfNumbers ( n )  

{   

     If n is equal to 1, the output is 1, otherwise the output is n + SumOfNumbers(n-1).

}

This is a recursive definition because the function refers to itself in its definition. The key part of the definition is that there is a single case for a specific input that does not refer to itself - but returns a value - allowing the function to escape from an infinite regress of definition. In the "SumOfNumbers" case, this is the output when given "1" as the input.  

One thing you'll notice as you work through the solution of SumOfNumbers(4) is you have to keep four intermediate answers before you can combine them into the final output:

SumOfNumbers(4) = 4 + SumOfNumbers(3)

SumOfNumbers(3) = 3 + SumOfNumbers(2)

SumOfNumbers(2) = 2 + SumOfNumbers(1)

SumOfNumbers(1) = 1

In a computer, storing each intermediate function result requires memory. So, recursive functions (assuming your computer language of choice supports recursive function definitions) can take longer to solve and may be limited by available memory to solve large inputs ( try SumOfNumbers(1000) on paper...) 

Let's look at another recursive function example - generating Fibonacci numbers.

The following code expresses the implementation of a function which returns the "nth" number in the Fibonacci sequence. Note how it  reads: the nth fibonacci number is the sum of the two previous fibonacci numbers (the first 2 numbers are always "1"):

def fibo(n):
    if n <= 2:
        return 1
    return fibo(n-1) + fibo(n-2)

This function runs just fine in Python up until you enter something like fibo(300) - at which point you will notice that Python is not optimizing this function as it will explode and set your computer on fire.

If the last statement in a recursive function is a call to itself (as it does in the above example) then it is possible to optimize the function by doing a "tail" recursive optimization. Some languages can detect a tail recursive definition and automatically optimize it. Python doesn't do this.

You can optimize it yourself by passing along extra parameters to carry the intermediate results into the next nested call.  This essentially turns the recursion into an iteration. Here's the tail recursive version:

def fibotail(n):
    def fibohelp(i,j,n):
        return fibohelp(j,i+j,n-1) if n>0 else j
    return fibohelp(0,1,n)

I'm taking advantage here of Python's ability to define nested functions. Fibotail calls its fibohelp function recursively - note the extra parameters to carry along the two previous results in the call.

To tell you the absolute truth, every time I write this code, I have to read it twice. I do not find it all intuitive. It is recursive, it is succinct code, and it will work efficiently on very large inputs. So it is optimized, but I would argue it's not worth the time to write it this way - as it loses the primary benefit of writing recursive function definitions: they can make certain algorithms easier to express and understand.

If your language of choice doesn't support automatic tail recursion optimization I'd recommend falling back on iteration to express your algorithm. I'd argue the following code at least captures the essence of the algorithm even if it is less brief and succinct.

def fiboloop(n):
    firstfibo = 1
    secondfibo = 1
    nextfibo = 1
    
    for x in range(1,n-1):
        nextfibo = firstfibo + secondfibo
        firstfibo = secondfibo
        secondfibo = nextfibo

    return nextfibo

As always, these are often matters of taste. however, if you are using a functional language that doesn't support loops and does not automatically optimize tail-recursive function definitions, then you'll possibly need to know how to write a hand-optimized tail-recursive code.