CODEWITHSUNDEEP
c#recursionpermutation
user13094861
user13094861

Reputation:

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

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?

Upvotes: 0

Views: 156

Answers (1)

Mulan
Mulan

Reputation: 135187

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

Upvotes: 1

Related Questions