经典实例讲解C#递归算法

 下面是汉诺塔的递归求解实现(C#代码)：

public static void hannoi(int n, string from, string buffer, string to)
  {
   if (n == 1)
   {
   Console.WriteLine("Move disk " + n + " from " + from + " to " + to);
   }
   else
   {
   hannoi(n - 1, from, to, buffer);
   Console.WriteLine("Move disk " + n + " from " + from + " to " + to);
   hannoi(n - 1, buffer, from, to);
   }
  }

其运行结果如图(大家可以跟上面的gif图片对比一下):

四 、排列组合

1、输出任意个数字母、数字的全排列

　　对于一个长度为n的串或者n个字符(数字、节点)组成的字符串数组，它的全排列共有A(n, n)=n!种。这个问题也是一个递归的问题。如1,2,3，全排列可得到：{123,132,213,231,312,321}。

用递归算法实现代码如下：

public static void Permutation(string[] nums, int m, int n)
  {
   string t;
   if (m < n - 1)
   {
   Permutation(nums, m + 1, n);
   for (int i = m + 1; i < n; i++)
   {
    //可抽取Swap方法
    t = nums[m];
    nums[m] = nums[i];
    nums[i] = t;
    
    Permutation(nums, m + 1, n);

    //可抽取Swap方法
    t = nums[m];
    nums[m] = nums[i];
    nums[i] = t;
   }
   }
   else
   {for (int j = 0; j < nums.Length; j++)
   {
    Console.Write(nums[j]);
   }
   Console.WriteLine();
   }
  }

调用代码如下：

static void Main(string[] args)
  {
   Nums = new string[] { "a", "b", "c" };
   Permutation(Nums, 0, Nums.Length);
   Console.ReadKey();
  }

这里传入一个string数组，abc三个字母来测试，输出如下图：

2、将全排列结果保存到链表中

　　有时候，我们需要将全排列的结果保存，然后做其他的处理，我们可以将结果保存到一个链表中。我们定义如下类作为链表的节点，代码如下：

public class Node
 {
  public string value { get; set; }
  public Node nextNode { get; set; }

  public Node(string value)
  {
   this.value = value;
   this.nextNode = null;
  }
 }

 此时声明全局变量，如下：

public static List<Node> NodeList = new List<Node>();

这个时候，我们修改Permutation方法，如下：

public static void Permutation(string[] nums, int m, int n)
  {
   string t;
   if (m < n - 1)
   {
   Permutation(nums, m + 1, n);
   for (int i = m + 1; i < n; i++)
   {
    //可抽取Swap方法
    t = nums[m];
    nums[m] = nums[i];
    nums[i] = t;
    
    Permutation(nums, m + 1, n);

    //可抽取Swap方法
    t = nums[m];
    nums[m] = nums[i];
    nums[i] = t;
   }
   }
   else
   {
   Node root = null;
   Node currentNode;
   for (int j = 0; j < nums.Length; j++)
   {
    currentNode = new Node(nums[j]);
    currentNode.nextNode = root;
    root = currentNode;
   }
   NodeList.Add(root);
   }
  }								 
 2/3   首页 上一页 1 2 3 下一页 尾页