Convert recursive algorithm into a loop

Learn
#1

One of the ways that haskell can be useful is to write algorithms at a high level of abstraction and then convert them by hand into other languages.
The problem is recursion, are there systematic methods to convert recursive algorithms into loops?
One example is mergesort, in haskell it is very simple and saves a lot of time. How can it be converted to a loop?
I am not referring to a specific language; pseudocode is fine.

#2

This is one approach Defunctionalize the Continuation

3 Likes
#3

If you mimic the stack call/backtracking behavior that recursion has you can convert a recursing algorithm into a loop. You do that using a stack.

Good examples of this are converting DFS algorithm that is inherently recursive into an iterative one using a stack

1 Like
#4

Also: Performance/Accumulating parameter - HaskellWiki

1 Like
#5

Most languages already support recursion. Some of them furthermore have good compilers (e.g., gcc) that optimize recursion as much as ghc does. There is zero motivation to hand-translate recursion into loops, in this the 21st Century of Our Lord already. This is not a Dark Age.

#6

To sum up all answers:

  1. make the recursive function tail recursive - this is the hard part of it.
  2. change the recursive function into a while-loop
  3. change the arguments of the recursive function into local variables that are set before entering the loop
  4. mutate the arguments (now local variables) and the accumulator instead of passing them into the recursive function
  5. return the accumulator from the loop

Let’s use a recursive function that has been seldom used for examples:

fac 0 = 1
fac n = n * fac (n - 1)

to tail call:

fac n = go n 1
  where 
    go idx acc = 
      if idx == 0 
        then acc
        else go (idx - 1) (acc * n)

to loop

function fac(n) {
  let idx = n;
  let acc = 1;
  while (idx > 0) {
    acc = acc * idx;
    idx = idx - 1;
  }
  return acc;
}
3 Likes
#7

Is there any automatic tool to do this? That takes haskell recursive code and spits out a loop in pseudocode.

#8

This is not entirely true - in my last job, we worked on a DSL where the parser, type checker, and elaborator were in Haskell, but the RTS was in Kotlin because a JVM execution environment fit the business case. JVM has a pretty small limit on the allowed size of a stack, and I found that manually CPSing a couple recursive functions, defunctionalizing the continuation, and converting that to an explicit state machine inside a for loop was a technique that worked well to get fast, readable code that didn’t blow the stack (“readable” to those who saw the recursive function used as a test oracle and read the comment about the conversion, at least!).

2 Likes
#9

I’m not aware of a general tool that will do this automatically. Laziness makes it complicated - most settings where I’d use that pseudocode are strict, so there would be a difficult impedance mismatch. But it would be a nice extra credit project in a first-year compilers course to do this for a strict subset of Haskell.

1 Like