converting to tail recursion-CodePudding

Consider a function g(x):

g(x) = x == 0 ? 0 : g(g(x - 1))

I don't think this is tail recursive, since the call to g(x) can be broken down into two parts:

let y = g(x - 1);
return g(y);

how to convert this to tail recursion?

CodePudding user response：

You can use continuation-passing style -

g'(x,return) =
  x == 0
    ? return(0)
    : g'(x - 1, x' =>        # tail
        g'(x', return))      # tail

Now write g to call g' with the default continuation -

g(x) = g'(x, x' => x')

Depending on the language you use, you may have to rename return to something else. k is a popular choice.

We can see this technique applied to other problems like fib -

fib'(x, return) =
  x < 2
    ? return(x)
    : fib'(x - 1, x' =>       # tail| first compute x - 1
        fib(x - 2, x'' =>     # tail| then compute x - 2
          return(x'   x'')))  # tail| then return sum

fib(x) = fib'(x, z => z)

Continuation-passing style is useful in other ways too. For example, it can be used to provide branching or early-exit behavior in this search program -

search(t, index, match, ifFound, notFound) =
  i >= length(t)
    ? notFound()
    : t[index] == match
        ? ifFound(index)
        : search(t, index   1, match, ifFound, notFound)

We can call search with continuations for each possible outcome -

search(["bird", "cat", "dog"],
  0,
  "cat",
  matchedIndex => print("found at: "   matchedIndex),
  () => print("not found")
)