转换为尾递归

Question

考虑函数 g(x):

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

我认为这不是尾递归，因为对 g(x) 的调用可以分为两部分：

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

如何将其转换为尾递归？

Answer 1

延续传球风格

您可以从直接样式转换为 continuation-passing style -

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

现在写g调用g'默认继续-

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

根据您使用的语言，您可能需要将 return 重命名为其他名称。 k 是一个受欢迎的选择。

另一个例子

我们可以看到这种技术应用于其他问题，例如 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)

其他用途

Continuation-passing 风格在其他方面也很有用。例如，它可用于在此 search 程序中提供分支或提前退出行为 -

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

我们可以为每个可能的结果调用 search 并继续 -

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

如何

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.

您之前可能使用过延续

如果你曾经运行听到有人说“回调”，他们真正的意思是延续。

"点击按钮时，继续程序event => ..."-

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

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

"读取文件内容后，继续程序(err, data) => ..."-

import { readFile } from 'fs';

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

转换为尾递归

converting to tail recursion

recursion

tail-recursion