Recursion Helper Functions and Guards

Recursion helper variables

Often you’ll find you need helper variables in recursion to keep track of things. You can get them by defining a helper function with more arguments. Analogy: arguments of the helper function are variables you update in your loop.

Here’s an example of how you would convert a loop (in Java or Python) into a recursive helper function in Haskell.

Java:

public String repeatString(int n, String str) {
    String result = "";
    while (n>0) {
        result = result+str;
        n = n-1;
    }
    return result;
}

Python:

def repeatString(n, string):
    result = ""
    while n>0:
        result = result+string
        n = n-1
    return result

Haskell:

repeatString n str = repeatHelper n str ""

repeatHelper n str result = if (n==0)
                            then result
                            else repeatHelper (n-1) str (result++str)

Prelude> repeatString 3 "ABC"
"ABCABCABC"

You might have noticed that the Java and Python implementations look a bit weird since they use while loops instead of for loops. This is because this way the conversion to Haskell is more straightforward.

This can be made a bit tidier by using pattern matching instead of an if:

repeatString n str = repeatHelper n str ""

repeatHelper 0 _   result = result
repeatHelper n str result = repeatHelper (n-1) str (result++str)

Here’s another example with more variables: computing fibonacci numbers efficiently.

Java:

public int fibonacci(int n) {
    int a = 0;
    int b = 1;
    while (n>1) {
        int c = a+b;
        a=b;
        b=c;
        n--;
    }
    return b;
}

Python:

def fibonacci(n):
    a = 0
    b = 1
    while n>1:
        c = a+b
        a = b
        b = c
        n = n-1
    return b

Haskell:

-- fibonacci numbers, fast version
fibonacci :: Integer -> Integer
fibonacci n = fibonacci' 0 1 n

fibonacci' :: Integer -> Integer -> Integer -> Integer
fibonacci' a b 1 = b
fibonacci' a b n = fibonacci' b (a+b) (n-1)

Take a while to study these and note how the Haskell recursion has the same format as the loop.

Sidenote: Haskell programs often use the apostrophe to name helper functions and alternative versions of functions. Thus the name fibonacci' for the helper function above. Names like foo' are usually read foo prime (like in mathematics).

I said earlier that this version of fibonacci is more efficient. Can you see why? The answer is that there are less recursive calls. The expression fibonacci' _ _ n calls fibonacci' _ _ (n-1) once, and this means that we can compute fibonacci' _ _ n in n steps.

This type of recursion where a function just directly calls itself with different arguments is called tail recursion. As you’ve seen above, tail recursion corresponds to loops. This is why tail recursion is often fast: the compiler can generate a loop in machine code when it sees tail recursion.

Guards

Before we move on to new types, let’s go over one more piece of Haskell syntax.

The if then else is often a bit cumbersome, especially when you have multiple cases. An easier alternative is Haskell’s conditional definition or guarded definition. This is a bit like pattern matching in that you have multiple equations, but you can have arbitrary code deciding which equation to use. Guarded definitions look like this:

f x y z
  | condition1 = something
  | condition2 = other
  | otherwise  = somethingother

A condition can be any expression of type Bool. The first condition that evaluates to True is chosen. The word otherwise is just an alias for True. It is used to mark the default case.

Examples

Here are some examples of using guards. First off, we have a function that describes the given number. Note how it is important to have the "Two" case before the "Even" case.

describe :: Int -> String
describe n
  | n==2      = "Two"
  | even n    = "Even"
  | n==3      = "Three"
  | n>100     = "Big!!"
  | otherwise = "The number "++show n

Here is factorial, implemented with guards instead of pattern matching. Unlike the pattern-matching version, this one doesn’t loop forever with negative inputs.

factorial n
  | n<0       = -1
  | n==0      = 1
  | otherwise = n * factorial (n-1)

You can even combine guards with pattern matching. Here’s the implementation of a simple age guessing game:

guessAge :: String -> Int -> String
guessAge "Griselda" age
    | age < 47 = "Too low!"
    | age > 47 = "Too high!"
    | otherwise = "Correct!"
guessAge "Hansel" age
    | age < 12 = "Too low!"
    | age > 12 = "Too high!"
    | otherwise = "Correct!"
guessAge name age = "Wrong name!"

Prelude> guessAge "Griselda" 30
"Too low!"
Prelude> guessAge "Griselda" 60
"Too high!"
Prelude> guessAge "Griselda" 47
"Correct!"
Prelude> guessAge "Bob" 30
"Wrong name!"
Prelude> guessAge "Hansel" 10
"Too low!"

Exercises:

All exercises can be found in Set2a and Set2b. Please pay attention in the title of the exercise in which file the exercises of this section can be found.

Exercises from 2a:

None for now :)

Exercises from 2b:

You can check your current points from the blue blob in the bottom-right corner of the page.