Getting started with writing a simple recursive program

While writing a recursive program is not a necessary skill, it opens doors to solving problems in new ways that might feel clunky to solve the iterative way.

Here is a step by step guide to convert an iterative function to a recursive function. The guide works well for cases where we accumulate a result in each iteration.

I’ll be using factorial of a number as an example.

1. Write it the iterative way

We use result variable to accumulate the answer while iterating from 1 through n

def factorial(n):
    result = 1
    for i in range(1, n + 1):
        result = result * i
    return result

2. Parameterize (with defaults) all the variables

Apart from n we are using result and i. We add them as function parameters and set the initial value as default value.

Our function signature would look like this:

def factorial(n, result=1, i=1):

3. Function body would be for loop’s body

We make the same updates to variables as in our for loop:

result = result * i
i = i + 1

At the end, call its own function with the updated variables

return factorial(n, result, i)

Our function now looks like this:

def factorial(n, result=1, i=1):
    result = result * i
    i = i + 1
    return factorial(n, result, i)

Refactor: We can directly pass the new values to the function call instead of mutating the variables

def factorial(n, result=1, i=1):
    return factorial(n, result * i, i + 1)

4. Add terminating condition

Add the same for loop’s terminating condition. When we exit our loop, we return the result. We’ll do the same here.

def factorial(n, result=1, i=1):
    if i > n:
        return result
    return factorial(n, result * i, i + 1)

5. Get rid of extra function parameters

This is where we need to think creatively to get rid of as many function parameters as possible.

i. Getting rid of i

n is used only for the termination condition and nowhere else in the logic. So if we reverse the order of iteration (n..1) our termination condition would be i == 0

def factorial(n, result=1, i=None):
    i = i or n # initialize i with n
    if i == 0:
        return result
    return factorial(n, result * i, i - 1)

Now we can clearly see n is not being used anywhere other than initialization. So we can merge n and i into a single variable

def factorial(n, result=1):
    if n == 0:
        return result
    return factorial(n - 1, result * n)

ii. Getting rid of result

To remove result parameter, we update the logic to return result instead of accumulating it. So we would get the following termination condition. Which makes sense, because factorial of 0 is 1.

if n == 0:
    return 1

Since the return value is now result we can apply the operation on the return value instead. Which would be:

return n * factorial(n - 1)

6. That’s it, we’re done

We now have a recursive function for calculating the factorial

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

Another example

Let’s take a popular interview question and apply the same formula to create a recursive function.

Problem: Chunk Array

Description: Given an array and chunk size as parameters, write a function that will divide the array into several subarrays where each subarray has a length of chunk size

# Step 1: iterative version
def chunk(arr, size):
    chunked = []
    index = 0
    while index < len(arr):
        chunked.append(arr[index:index + size])
        index += size
    return chunked

# Step 2,3,4: add function parameters, body and terminating condition
def chunk(arr, size, index = 0, chunked = []):
    if index >= len(arr):
        return chunked
    return chunk(arr, size, index + size, chunked + arr[index: index + size])

# Step 5.1: get rid of index variable by cutting out the
# chunked part of the arr and assume index is always 0
def chunk(arr, size, chunked = []):
    # update the termination condition accordingly
    if len(arr) == 0:
        return chunked
    chunked.append(arr[:size])    
    return chunk(arr[size:], size, chunked)

# Step 5.2: get rid of `chunked` variable by returning
# the result and extracting the operation outside
def chunk(arr, size):
    # termination condition
    if len(arr) <= size:
        return [arr]
    return [arr[:size]] + chunk(arr[size:], size, chunked)

The final code looks like a recursive mathematical definition of a function. If we already have the definition, it would be as easy as writing the same with a programming language. So, often finding a recursive solution would be about finding such definitions that can solve the problem.

While this seems more mathematical, I personally feel recursive programs are best for solving problems involving combinations and patterns. I’ll be writing an article about this pretty soon, subscribe to get notified.