How to convert this function from recursive to tail-recursive?

Question

I have this method:

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

which gives all permutations of the list 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 tail-recursive?

Tail recursion just involves reassigning `lst` and looping back to the beginning of the function (obviously only possible if there are no more inner loop iterations remaining) — Wyck, May 20 '20 at 14:32
@Wyck So is there any way to make it iterative? I heard every recursive has an iterative equivalent. — , May 20 '20 at 14:39
If you have a stack, yes. Without a stack, no. Tail-recursion alone won't do it. — Wyck, May 20 '20 at 14:41
Without a stack, you can do permutations via the _next lexicographical permutation_ algorithm. [Description](https://www.nayuki.io/page/next-lexicographical-permutation-algorithm). [C# Implementation](https://www.nayuki.io/res/next-lexicographical-permutation-algorithm/nextperm.cs) — Wyck, May 20 '20 at 14:51
Not a dupe because it's Java, but you can probably use [this](https://stackoverflow.com/questions/11915026/permutations-of-a-string-using-iteration). — ggorlen, May 20 '20 at 15:10
Aside: `List tmp = new List(permutation(remLst));` - you don't need a copy here, you can just do `List tmp = permutation(remLst);`. — 500 - Internal Server Error, May 20 '20 at 15:23

score 1 · Accepted Answer · answered May 20 '20 at 15:56

Consider this recursive Fibonacci program -

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

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

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

How to convert this function from recursive to tail-recursive?

1 Answers1