如何将此函数从递归转换为迭代?

问题描述

我有这种方法:

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的所有排列.

这个想法是一个接一个地提取所有元素，将它们放在第一个位置，然后重复列出剩余的元素. 此处.

The idea is to one by one extract all elements, place them at first position and recur for remaining list. Python equivalent here.

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

How to convert it from recursive to iterative?

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

I heard it can be done by converting it to tail-recursion and Stack, but I don't know how.

推荐答案

考虑此递归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进行了两次调用，对吗?不-

For any given function, only the last operation can be in tail position. So tail recursion is impossible for our program because there are two calls to Fibonacci right? No -

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() {
    // ...
  }
}

---

延续传递样式(如上所示)很容易使我们转换将任何递归程序转换为迭代程序；并且无需显着更改程序的形状.可以使用CPS技术对Permutation进行类似的转换-

---

Continuation passing style (demonstrated above) easily allows us to convert any recursive program to an iterative one; and without having to dramatically change the program's shape. Permutation can be similarly transformed using a CPS technique -

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

这篇关于如何将此函数从递归转换为迭代?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！