Eirik Tsarpalis' blog

On the Significance of Recursion

Advertisements

During a recent conversation with a group of F# developers, I started making the case for recursion and its importance in day-to-day programming. My peers reacted with surprise to this opinion of mine, responding that they thought that recursion is an inherently inefficient way of defining programs.

We are taught this rule when studying procedural languages: “for optimal results, just use iteration”. In functional languages however, this is not necessarily true: tail-recursive functions are optimized into imperative loops at compile time and most recursive functions can be readily transformed into tail-recursive workflows by applying accumulators or CPS. These FP fundamentals are what make the functional paradigm a feasible alternative to the imperative style.

I was thus legitimately surprised to discover that working F# programmers carried this attitude towards recursion, which made me wonder whether this could be an artifact of how the language is being taught to FP newcomers. I researched some of the popular online material and did a bit of asking around which seemed to confirm my suspicion: there exists a tendency for de-emphasizing recursion in beginner F# educational material. An important reason is that the topic of recursion itself can appear puzzling and counter-intuitive to beginners: quoting Graham Hutton

Defining recursive functions is like riding a bicycle: it looks easy when someone else is doing it, may seem impossible when you first try to do it yourself, but becomes simple and natural with practice.

Omitting recursion can also be justified by a desire to appear pragmatic; recursion has a reputation for being too academic, a mathematical trivium that is only useful when defining Fibonacci numbers but not relevant in real code. Algorithms should be declared by composing available combinators, and if everything fails we can always fall back to the imperative style. Recursion is relegated to the “Advanced” chapters, bundled together with other academic curiosities such as call/cc and catamorphisms.

An Example

While there are merits in this stance, I claim that avoiding recursion entirely in expression-based languages comes with some very important limitations. I will try to illustrate why using an example. Consider the core combinator

val List.tryFind : ('T -> bool) -> 'T list -> 'T option

which performs linear searches on its supplied list, returning the first element that happens to satisfy the supplied predicate. This is a simple yet extremely useful combinator that is often finding use in F# codebases. It works very well for most applications, assuming our predicate is a regular lambda.

But what happens if the predicate is of type 'T -> Async, in other words asynchronous? We would probably require a variation of tryFind, namely

val tryFindAsync : ('T -> Async<bool>) -> 'T list -> Async<'T option>

which however is not available the core library. In such circumstances, F# developers will have to improvise.

As an exercise, let’s attempt to provide a good implementation that avoids recursion. A novice user would quickly end up with the following solution:

let tryFindAsync (pred : 'T -> Async<bool>) (inputs : 'T list) =
    async { return List.tryFind (pred >> Async.RunSynchronously) inputs }

which is evidently a misguided solution, since it invalidates the purpose of asynchrony.

The requirement for asynchrony could still be satisfied using smarter manipulation of generic combinators, as seen in the following example:

let tryFind (f : 'T -> Async<bool>) (ts : 'T list) =
    let folder acc t = async {
        let! result = acc
        match result with
        | Some _ -> return result
        | None ->
            let! success = f t
            return if success then Some t else None
    }

    List.fold folder (async.Return None) ts

In this case, we are folding over asynchronous computations, so the final result is a non-blocking asynchronous workflow that can be consumed accordingly. There are however two problems with this approach:

  1. The solution is too smart for its own good. Sure, folding over functions feels good to the person that came up with it, however there is a nontrivial cognitive overhead associated with what should be a very simple task. In the context of a bigger team, such heroics aren’t appreciated.
  2. More importantly, fold operations always traverse the entire input list. The point of tryFind is that it should stop as soon as a result is found. By delegating iteration to other combinators, we lose the ability to tune aspects of control flow. Assuming our input type allowed for infinite lists (for instance IEnumerable), this approach would necessarily result in non-terminating computation.

An Imperative Solution

Let us now try addressing the same problem using the imperative style. First, here’s how it could be defined elegantly using C#:

async Task<Option<T>> TryFindAsync<T>(Func<T, Task<bool>> predicate, IEnumerable<T> inputs)
{
    foreach (var t in inputs)
        if (await predicate(t)) return Option.Some(t);
    
    return Option.None<T>();
}

What happens if we attempt to port this implementation to F#? First of all, F# is an expression-based language, which means that return keywords (in the imperative sense) are not permitted. Rather, we need to introduce additional variables to simulate breaks:

let tryFindAsync (predicate : 'T -> Async<bool>) (ts : 'T list) = async {
    let mutable result = None
    let mutable ts = ts
    while Option.isNone result && not (List.isEmpty ts) do
        let head :: tail = ts
        let! r = predicate head
        if r then result <- Some head
        else ts <- tail

    return result
}

Few would disagree with the conclusion that this solution is ugly and easy to get wrong. The lack of return, break and continue constructs in expression-based languages is the primary reason why an imperative approach is awkward here.

Real-Word Recursion

This is precisely where recursion comes in handy. It can be used to effectively emulate any sort of imperative break in expression-based programs:

let rec tryFind (f : 'T -> Async<bool>) (ts : 'T list) = async {
    match ts with
    | [] -> return None
    | head :: tail ->
        let! r = f head
        if r then return Some head
        else return! tryFind f tail
}

Similar examples can be provided that illustrate how break and continue constructs can be emulated using recursion.

Conclusion

When working with expression based languages, recursion is an essential tool for achieving control flow patterns typically only attainable via imperative constructs. In the context of F#, working programmers can only benefit from acquainting themselves with the standard syllabus of common recursion patterns commonly used in FP languages.

Advertisements