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.
Top comments (0)