如何将此功能从递归转换为迭代？

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的here。

如何将其从递归转换为迭代？

我听说可以通过将其转换为尾递归和Stack来完成，但我不知道如何。

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));
    }
  }
}

对于任何给定功能，只有最后一个操作可以在tail position中。那么对于我们的程序而言，尾部递归是不可能的，因为对Fibonacci的调用是[[two吗？否-

class MainClass {

  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
          )
        );
  }

  public static int Fibonacci(int n) {
    return FibCont(n, a => a);
  }

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

Continuation passing style（如上所示）很容易使我们将
any

递归程序转换为迭代程序；并且无需显着更改程序的形状。 Permutation可以使用CPS技术类似地转换-

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

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