C#递归算法和排列算法
时间：2022-12-31 12:21:15|栏目：.NET代码|点击： 次
一、递归算法
递归：你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门，你继续打开它。若干次之后，你打开面前的门后，发现只有一间屋子，没有门了。然后，你开始原路返回，每走回一间屋子，你数一次，走到入口的时候，你可以回答出你到底用这你把钥匙打开了几扇门。
循环：你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门（若前面两扇门都一样，那么这扇门和前两扇门也一样；如果第二扇门比第一扇门小，那么这扇门也比第二扇门小，你继续打开这扇门，一直这样继续下去直到打开所有的门。但是，入口处的人始终等不到你回去告诉他答案。
1、定义：
在数学与计算机科学中，递归(Recursion)是指在函数的定义中使用函数自身的方法。实际上，递归，顾名思义，其包含了两个意思：递 和 归，这正是递归思想的精华所在。
2、实例：
static void Main(string[] args)
{
int[] sum = new int[30];
for (int i = 0; i < sum.Length; i++)
{
sum[i] = process1(i);
Console.WriteLine(sum[i]);
}
}
public static int process1(int a)
{
if (a == 0 || a == 1) return 1;
return process1(a - 1) + process1(a - 2);
}
3、阶乘算法：
public static int process2(int n)
{
if (n == 1) return 1;
return n * process2(n - 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
{
#region 存放到List
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);
#endregion
#region 打印控制台
for (int j = 0; j < nums.Length; j++)
{
Console.Write(nums[j]);
}
Console.WriteLine();
#endregion
}
}
调用算法：
static void Main(string[] args)
{
Nums = new string[] { "a", "b", "c" };
Permutation(Nums, 0, Nums.Length);
Console.ReadKey();
}
