Recursion in Python
NOTE: All the code below has been tested using Python 3.8.12 and some of the syntax might not be compatible with older versions.
One of the main selling points of any functional programming language is recursion or rather an elegant way you can implement recursive function using one’s syntax. In this article I want to show that Python can be easily adapted to be written in a functional way proving it’s a trully multi-paradigm language.
Everyone knows classical example of recursion using Fibonacci sequence, so let’s take a look at the corresponding Python code for it.
def fib(n: int) -> int:
We have a function accepting a number and returning an element of the Fibonacci sequence corresponding to that number. Each recursive function should have a base case (also known as edge case) and essentially it’s a branch of code which halts or returns something immediatelly without making any subsequent recursive calls. Then we have two recursive function calls calculating two previous numbers of the sequence and basically that corresponds to the definition where each number is just a sum of two prior ones in a sequence.
Most of the functional languages are also known to be statically typed, so we are also using type annotations within our code examples to make them look more functional-ish.
Now let’s implement a couple of frequently used common functions to illustrate such things can be implemented concisely in a recursive fashion.
Our first subject is
minimum function returning target element from the list.
As usually we start from a base case knowing that maximum element of the list containing only one element is the element itself.
The biggest element of the whole list is either current one or the biggest element from the rest of the sequence. Here we use list destructuring to seamlessly extract first element from the list as well as its tail into two different variables.
Same result can be accomplished using approach below (in case you are not comfortable with such a syntax):
arr = [1, 2, 3, 4]
Another option is to use slices on the list:
arr = [1, 2, 3, 4]
Same logic applies to the
minimum function, but here instead of comparison we invoke min built-in function.
from typing import List
Below you can find couple of extra functions just to demonstrate how similar their structure is and how fluently any structure can be translated into recursive calls.
replicatetakes a number
nand a value
valand returns a list containing
ncopies of the same
def replicate(n, val):
take- given a number
nand a list
arrit returns first
nelements from that list
def take(n, arr):
3, [0, 1, 2, 3, 4])take(
elem- for the value
valprovided and a list
arrit returns whether a list contains that element
def elem(val, arr) -> bool:
1, 2, 3]arr1 = [
reversesimply reverses a list
1, 2, 3, 4, 5])reverse([
ziptakes two lists and zips them together. It returns one list each element being a pair of matching elements from input lists. In case one list is shorter the resulting list would not contain items from the longer list that do not match with anything in the end.
def zip(xs, ys):
Example invocation (resulting list does not contain
d element as it doesn’t match with anything from the first list):
1, 2, 3]arr1 = [
As an extra exercise you can start by taking any function from itertools module and trying to come up with equivalent recursive code. Most of the functions there have rough code implementation provided within the documentation page above, so it would be much easier to understand what kind of logic you are trying to achieve.
There are a lot of graph traversal algorithms which are easier to implement using recursive functions as well as this example of quicksort algorithm because their own definitions are declared in recursive terms. To accomplish sorting we start with pivot element which in the simplest case is just a first element of our list and place it between two partitions: first one is an array of sorted elements which are less or equal to our pivot and the second one is an array of sorted elements greater than that.
As you can see there is nothing complex about recursion and some implementations can be even simpler then their iterative counterparts. Sometimes recursive code might be a bit harder to debug, so when in doubt always stick with the solution that is easier for you to understand and maintain. Otherwise go ahead and implement your new feature using recursive functions. Happy coding!