/ python

Recursion Exercises

Recursions are one of those things that are easy to understand in theory, but in practice can take some getting used to. If you're struggling with it here are some exercises that might help you along.

Implement Loops Using Recursion

Write a function that prints Hello World n times without using loops.

Usage example:


# Prints:
# 0: Hello World
# 1: Hello World
# 2: Hello World
# 3: Hello World
# 4: Hello World

What is the maximum value you can pass to the function without raising an exception?

Evaluating Expressions

So loops are probably not the best candidate to be replaced by recursions. Nevertheless they helped us grasp a better understanding of the concept.

Now let's move to something more interesting: Evaluating mathematical expressions. Given the following python class:

import operator

class Expression:
    def __init__(self, op, x, y):
        self.op = op
        self.x  = x
        self.y  = y

Write a function called val that takes such an expression and prints its value. For example the following code should print 11:

e = Expression(
        Expression(operator.mul, 2, 2),
        Expression(operator.mul, 3, 2)


Matrix Region Detection

As illustrated by the previous exercise, multiple recursive calls can be combined to create more complex solutions. In the above you might have used the recursive call twice (one for each part of the expression).

Next let's move to finding regions in a matrix. You are given a 8x8 matrix where # marks a taken square and . marks a free square:


Print out a version of the matrix with each region "marked" in a different letter. A region is a group of taken squares each adjacent to at least one other in the group vertically or horizontally (no diagonals).

For example given the above input your program should print:


Cartesian Product

It's normal to write code above or below the recursive call, and use the returned data in many ways. Write a function that takes any number of arrays in Python and combines their elements to print a cartesian product.

For example given the following call:

x = ['a', 'b']
y = ['x', 'y']
z = ['1', '2']

prod(x, y, z)

Your function should return the array:

['ax1', 'ax2', 'ay1', 'ay2', 'bx1', 'bx2', 'by1', 'by2']

Keep in mind the function can be called with any number of arrays, so a hard coded list comprehension won't work here.

Parenthesis Matching

Another case of using the recursive result in a complex evaluation is parenthesis matching functions. Let's finish by writing a function that takes an input and returns if its parenthesis are balanced.

For example the following should all return False:


But the following should all return True: