如何将这个函数从递归转化为尾部递归？

Question

我有这个方法。

static List<string> permutation(List<string> lst)
{
    switch (lst.Count)
    {
        case 0:
        case 1:
            return lst;
        default:
            List<string> l = new List<string>();


            for (int i = 0; i < lst.Count; i++)
            {
                string m = lst[i];
                List<string> remLst = lst.Except(new List<string> { m }).ToList();

                List<string> tmp = permutation(remLst);
                for (int i2 = 0; i2 < tmp.Count; i2++)
                {
                    l.Add(m + tmp[i2]);
                }
            }
            return l;
    }
}

它给出了列表中所有的排列组合。lst.

这个想法是逐一提取所有元素，将它们放在第一个位置，然后递归剩余的列表。相当于Python 此处.

如何把它从递归转换为尾部递归？

Answer 1

考虑这个递归的 Fibonacci 节目-

using System;

class MainClass {

  public static int Fibonacci(int n) {
    if (n < 2)
      return n;
    else
      return Fibonacci(n - 1) + Fibonacci(n - 2);
  }

  static void Main() {
    for (int i = 0; i < 15; i++) {
      Console.WriteLine(Fibonacci(i));
    }
  }
}

对于任何给定的函数，只有最后一个操作可以在 尾部位置. 所以尾部递归对于我们的程序来说是不可能的，因为在我们的程序中存在着 两种 呼吁 Fibonacci 对吗？不对

class MainClass {

  public static int Fibonacci(int n) {
    return FibCont(n, a => a); // <- call helper
  }

  private static T FibCont<T>(int n, Func<int, T> k) {
    if (n < 2)
      return k(n);
    else
      return
        FibCont(n - 1, a =>       // <- tail call
          FibCont(n - 2, b =>     // <- tail call
            k(a + b)              // <- tail call
          )
        );
  }

  static void Main() {
    // ...
  }
}

---

连续传球方式 (如上所示)很容易让我们将 任何 递归程序转变为迭代程序；而且不必大幅改变程序的形状。Permutation 可以使用CPS技术进行类似的转换---------------------------------------------。

static List<string> Permutation(List<string> lst) {
  return PermCont(lst, a => a) // <- call helper
}

static T PermCont<T>(List<string> lst, Func<List<string>, T> k) {
  switch (lst.Count) {
    case 0:
    case 1:
      return k(lst); // <- send answer to k
    default:
      string m = lst[0]; // <- first item
      List<string> remLst = lst.Except(new List<string> { m }).ToList();

      // remLst represents the smaller problem
      // solve the smaller problem and get the result
      return PermCont(remLst, result => {
        // result contains the permutations of remLst
        // construct the answer using remLst and m
        // answer = ... 
        return k(answer); // <- send answer to k
      })
  }
}