converting to tail recursion

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?

continuation-passing style

You can convert from direct style to 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.

another example

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

# direct style
fib(x) =
  x < 2
    ? x
    : fib(x - 1) + fib(x - 2) # "+" has tail position; not fib

# continuation-passing style
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)

other uses

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")
)

how to

A function written in continuation-passing style takes an extra argument: an explicit "continuation"; i.e., a function of one argument — _wikipedia

(* direct style *)
add(a, b) = ...

(* continuation-passing style takes extra argument *)
add(a, b, k) = ...

When the CPS function has computed its result value, it "returns" it by calling the continuation function with this value as the argument.

(* direct style *)
add(a, b) =
  a + b

(* continuation-passing style "returns" by calling continuation *)
add(a, b, k) =
  k(a + b)         (* call k with the return value *)

That means that when invoking a CPS function, the calling function is required to supply a procedure to be invoked with the subroutine's "return" value.

(* direct style *)
print(add(5, 3))                  (* 8 *)

(* continuation-passing style *)
add(5, 3, print)                  (* 8 *)

Expressing code in this form makes a number of things explicit which are implicit in direct style. These include: procedure returns, which become apparent as calls to a continuation; intermediate values, which are all given names; order of argument evaluation, which is made explicit; and tail calls, which simply call a procedure with the same continuation, unmodified, that was passed to the caller.

you've probably used continuations before

If you've ever run into someone saying "callback", what they really mean is continuation.

"When the button is clicked, continue the program with event => ..." -

document.querySelector("#foo").addEventListener("click", event => {
  console.log("this code runs inside a continuation!")
})

<button id="foo">click me</button>

"When the file contents are read, continue the program with (err, data) => ..." -

import { readFile } from 'fs';

readFile('/etc/passwd', (err, data) => {
  if (err) throw err;
  console.log(data);
});

converting to tail recursion

Related

Recent Posts