Recursion in Python, an exploration
Recursion is one of those ideas that may seem out of reach, likely from a higher plane of programming existence. Something that A. You don’t really know why it’s a thing and B. You don’t think you would ever need to utilize it. After all, there are no Functional Programming languages in the Top 10 of the TIOBE index as of this writing. Think again, and again…
Perhaps you’re right, recursion is only useful for a coding interview and otherwise FORGET IT. However, I am of the opinion that learning different programming paradigms, and the way in which they parse problems, will ultimately make you a better data scientist/coder. Learning a new paradigm exposes you to new ways of thinking and different ways to structure your code. “This is the way we’ve always done it” won’t be a part of your verbal repertoire with this attitude. Consequently, you’ll learn more and have a better handle on solving the data challenges that come your way. Plus, if you like math like I do, and let’s face it if you are doing data science and don’t like math, then LEAVE NOW (sorry for the tone, I love you), then you will find the exercise enjoyable in its own right.
What is Recursion?
To introduce recursion, let’s make a simple, hypothetical case that compares solutions. You have an array or list of numbers that need to be squared before they are utilized by the rest of your program. We could use a for loop or list comprehension in python to create the squared version as such.
# Set array
my_array = [10,11,12,13,14,15]# Method 1
# Create a new squared array with for loop (can be considered an anti-pattern)
squared_array = []
for num in my_array:
squared_array.append(num*num)# Method 2
# Create a new squared array with list comprehension, a bit more beautiful and concise
my_squared_array = [x*x for x in my_array]
Typically when we loop over values in an imperative language like Python, we are using a for loop or a while loop. These are the constructs we are used to and we use them so often, they are second nature. But what if for and while loops got axed from python tomorrow? Aside from a majority of the world ceasing to function, we have the more pressing issue…how to use recursion now??
Recursion Intro: Squared Array
We can’t use a list comprehension, so let’s use our new pal recursion to square our array. For this, we need to write a new function.
# Set array
my_array = [10,11,12,13,14,15]# Define our recursive, squared function that returns a new array
def squares(an_array, n=None, ret_array=None):
if n == None:
n = len(an_array)
ret_array = []
pos = len(ret_array)
squared = an_array[pos] ** 2
ret_array.append(squared)
if n-1 == 0:
return ret_array
else:
return squares(an_array, n-1, ret_array)
Ok, that’s a bit ugly and verbose when a list comprehension would suffice, but it shows that we can use recursion in place of a for loop. The function begins by initiating a new array that holds our square values, uses n as a counter to determine where we are as we go over the array by position, then it calls itself until we have gone through the entire array and subsequently have our new squared array.
Helpful Hints
Think of a recursive function as a bit of code that does not only reside in one place in memory. Sure, the function is defined in one place, but can be called multiple times as data is passed into it. This is termed the Call Stack. Don’t think about it like a Python eating its own tail, though many R users would be cheering. Think about it like a bunch of clones passing a small box, each putting in a coin, then passing the box to the next clone. Ok, maybe now you’re even more confused. Going over the following 3 cases will be helpful to drive this point home and clear any confusion you may have.
Recursion Case 1: Canonical Factorials
Let’s use recursion to do what everyone who has ever touched recursion has done, calculate a factorial. Who else loves discrete mathematics!?
def factorial(num):
if num == 1:
return 1
return num*factorial(num-1)A factorial of n (notation as n!) is the product of all positive integers less than n. It is an operation on an arbitrary number defined as n! = n * (n-1) * (n-2)…(1!), where 1! = 1. This is what is called the stopping condition in our code. This idea is very important for recursion because without it, our code could go into an infinite loop, causing “a time paradox, the results of which could cause a chain reaction that would unravel the very fabric of the space time continuum and destroy the entire universe.” — Doc Brown
Say what?
Here’s a helpful way to visualize our factorial func for the case of 4!.
factorial(4) = 4*factorial(3) = 4*3*factorial(2) = 4*3*2*factorial(1) = 4*3*2*1 = 24
Each instance of the factorial function is the same as we have defined in def factorial(), but is a new instance that is taking the results of a previous factorial function instance and passing a new result on, all beginning with the base case of 1, in which case it all rolls up into the final calculation.
Recursion Case 2: Sum of First N Integers
Here’s how to use recursion to sum the integers between 0 and n
def sum_n(n):
if n == 0:
return 0
return n + sum_n(n-1)sum_n(1000)Outputs:
500500
Let’s check our result with the closed form version of the same operation, to make sure we defined our recursive function correctly. Spot checks are always a good idea, because as Richard Feynman said: “The first principle is that you must not fool yourself — and you are the easiest person to fool.” Insert I and myself into the quote to make it personal.
def check_sum(n):
return int(n*(n+1)/2)check_sum(1000)Outputs:
500500
Recursion Case 3: Compound Interest
You have probably seen the formula for compound interest before.
Since we have a number (1+r) that is raised to an exponential, then we can use recursion to calculate our future value FV.
def future_val(pv, rate, t):
if t == 0:
return pv
pv = pv*(1+rate)
return future_val(pv, rate, t-1)The previous function assumes a compounding rate of n=1. That means we only compound once per period t, where t is usually meant to refer to a years time. Let’s extend our example to include different compounding rates, such as monthly.
def future_val_n(pv, rate, t, n):
if t == 0:
return pv
pv = future_val(pv, rate/n, n)
return future_val_n(pv, rate, t-1, n)We’ve been able to recycle our future_val function, and extend it so that we are compounding n times per time period t. Does our function work?
future_val_n(1000, 0.07, 20, 12)Outputs:
4038.73# Now we check our value from future_val_nprint(1000*(1+0.07/12)**(20*12))Outputs:
4038.73
Final Words
Remember a few things
- We don’t have to have a pure functional language to begin using functional programming techniques in our code
- Python is not a pure functional language (of course), but borrows many features from them, such as functions as first class objects and list comprehensions to name a couple.
Given these two items, we then realize that python has a limit to the number of times a function can be called recursively. This limit is defined here:
sys.getrecursionlimit()Outputs:
3000
If we run our sum_n function with n>3000, it will throw a RecursionError even though the function works for a recursion depth less than the limit. This is something to think about when incorporating these types of functions into your python code base.
Now that you know recursion, you will start to see things differently, and perhaps have some creative solutions up your sleeve for your next project. I hope this has been a fun and informative intro to recursion and the functional programming paradigm!
