TDD with Recursion

Posted on by

Recursion means you define something in terms of itself. Some data fits naturally with recursion, e.g., trees. We’ll look at how to use TDD with recursion.

We’ll use a tree for our running example. A (binary) tree is either a leaf, or a node with left and right subtrees. Much like mathematical induction, where you prove something holds for all numbers, in recursion there is (at least one) base case and one or more recursive cases. 

Expressions and Recursion

Expressions fit naturally as trees. Let’s say an expression can be a number, a variable, or a sum or difference of two expressions. (We could obviously add more base cases and more operators.)

The expression (3-4)+2

Here’s an implementation of Expression in Swift. One thing to note is the word indirect – it declares that this is a recursive definition, with Expressions containing Expressions. The other thing to know is that each case defines an alternative, and may have its own particular data. 

indirect enum Expression {
  case number(Int)
  case variable(String)
  case plus(Expression, Expression)
  case minus(Expression, Expression)
}

TDD of Evaluation Using Recursion

Here’s how to evaluate an expression: numbers evaluate to their value, variables look up their value in a dictionary, and operators apply themselves to the value of their left and right subtrees.

For TDD with recursion: start with one or more base cases, then do the recursive cases. In most cases I’ve seen, you can do the other base cases before or after the recursive ones.

First the base cases, number and variable:

   XCTAssertEqual(Expression.number(3).evaluate([:]), 3)

   XCTAssertEqual(Expression.variable("x").evaluate(["x":7]), 7)
   XCTAssertEqual(Expression.variable("x").evaluate(["a":7]), 0)

Then the recursive ones, plus and minus; other operators would be analogous:

    XCTAssertEqual(
      Expression.plus(
        Expression.number(2),
        Expression.number(3))
      .evaluate([:]),
      5)

   XCTAssertEqual(
      Expression.minus(
        Expression.number(2),
        Expression.number(5))
      .evaluate([:]),
      -3)

I didn’t use any variables in the operator tests. Do I worry? Not too much, since they only depend on evaluate() doing its job on the subtrees. Similarly, I didn’t check that operators could have another operator in their left or right subtree. 

To remove the last traces of doubt, I may use an elaborative test: one I expect to pass without me writing any new code:

typealias E = Expression  // save some typing:)
    
let expression =
    E.plus(
      E.minus(
        E.minus(
          E.variable("x"),
          E.number(2)
        ),
        E.plus(
          E.number(1),
          E.variable("y")
        )
      ),
      E.plus(
        E.variable("x"),
        E.minus(
          E.number(4),
          E.number(3)
        )
      )
    )

    let values = ["x":5, "y":7]

    XCTAssertEqual(
      expression.evaluate(values),
      1)

(This passed on the first try.)

Here’s the code for evaluate():

  func evaluate(_ values: [String:Int]) -> Int {
    switch self {
    case .number(let value) :
      return value

    case .variable(let name):
      return values[name] ?? 0

    case .plus(let left, let right):
      return left.evaluate(values) + right.evaluate(values)

    case .minus(let left, let right):
      return left.evaluate(values) - right.evaluate(values)
    }
  }

For TDD with recursion: first do one or more base cases, then do the recursive cases. Test-drive the other base cases before or after the recursive ones.

TDD for Conversion to Postfix

Let’s work through another example. Instead of evaluating an expression in place, we might want to compile it. A common approach is to compile an expression to postfix, which can be evaluated later using a stack.

The rules are:

  • a number or variable writes its value or name to the output
  • An operator writes the postfix for the left side, the postfix for the right side, then the operator character

We’ll just generate text; a real application would probably create a stream of tokens. 

Here are the tests. They were written and made to pass one at a time.

   XCTAssertEqual(E.variable("x").postscript(), "x ")
   XCTAssertEqual(E.number(17).postscript(), "17 ")

   XCTAssertEqual(
      E.plus(E.number(2), E.number(3)).postscript(),
      "2 3 + ")

   XCTAssertEqual(
      E.minus(E.number(2), E.number(3)).postscript(),
      "2 3 - ")

   let expression =
    E.plus(
      E.minus(
        E.minus(
          E.variable("x"),
          E.number(2)
        ),
        E.plus(
          E.number(1),
          E.variable("y")
        )
      ),
      E.plus(
        E.variable("x"),
        E.minus(
          E.number(4),
          E.number(3)
        )
      )
    )

    XCTAssertEqual(
      expression.postscript(),
      "x 2 - 1 y + - x 4 3 - + + ")

Here’s the full implementation:

  func postscript() -> String {
    switch self {
    case .variable(let name):
      return "\(name) "

    case .number(let value):
      return "\(value) "

    case .plus(let left, let right):
      return "\(left.postscript())\(right.postscript())+ "

    case .minus(let left, let right):
      return "\(left.postscript())\(right.postscript())- "
    }
  }

This went together very easily, and its overall shape resembles the first solution.

Summary

Recursive structures fit well with recursive functions; they often yield a succinct solution that feels “obvious”. (There are particular situations that might need to avoid recursion, or need to add mechanism to avoid the risk of stack overflow, but they pay extra to do that.)

We’ve demonstrated how to use TDD to create recursive methods: develop at least one base case, then use that to test-drive the recursion cases. You can do the other base cases at any time. You might use one final “do it all” test to confirm that things work as expected for a big example.