经典实例讲解C#递归算法
作者:雲霏霏 时间:2022-04-11 22:34:16
目录
一 、递归算法简介
二 、Fibonacci数列和阶乘
1、 Fibonacci数列
2、阶乘
三 、汉诺塔问题
四 、排列组合
1、输出任意个数字母、数字的全排列
2、将全排列结果保存到链表中
一 、递归算法简介
在数学与计算机科学中,递归是指在函数的定义中使用函数自身的方法。
递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。
递归算法解决问题的特点:
(1) 递归就是在过程或函数里调用自身。
(2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。
(3) 递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。在实际编程中尤其要注意栈溢出问题。
借助递归方法,我们可以把一个相对复杂的问题转化为一个与原问题相似的规模较小的问题来求解,递归方法只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。但在带来便捷的同时,也会有一些缺点,也即:通常用递归方法的运行效率不高。
二 、Fibonacci数列和阶乘
1、 Fibonacci数列
提到递归,我们可能会想到的一个实例便是斐波那契数列。斐波那契数列就是如下的数列:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …,总之,就是第N(N > 2)个数等于第(N - 1)个数和(N - 2)个数的和。用递归算法实现如下:
public static int Fibonacci(int n)
{
if (n < 0) return -1;
if (n == 0) return 0;
if (n == 1) return 1;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
2、阶乘
还有就是求一个数的阶乘,也会用到递归,这个比较简单,直接给出实现代码,如图:
public static int Factorial (int n)
{
int sum = 0;
if (0==n)
return 1;
else
sum = n * Factorial(n 一1) ;
return sum;
}
三 、汉诺塔问题
汉诺塔是根据一个传说形成的数学问题:
汉诺塔示意图(图片来自网络)
有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:
1、每次只能移动一个圆盘;
2、大盘不能叠在小盘上面。
提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须遵循上述两条规则。
问:如何移?最少要移动多少次?
下面是汉诺塔的递归求解实现(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);
}
}
这样,我们执行了Permutation方法后,就将结果保存到链表中了。用的时候,我们只要遍历NodeList就可以了。如图:
递归算法就先说到这里了。谈到算法,就必需提数据结构,看来真的要“学到老了”~~
来源:https://www.cnblogs.com/yunfeifei/p/4272912.html
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
java实现钉钉机器人消息推送的示例代码
![](https://img.aspxhome.com/file/2023/5/82005_0s.png)
Spring事务失效的一种原因关于this调用的问题
Java使用备忘录模式实现过关类游戏功能详解
![](https://img.aspxhome.com/file/2023/2/60782_0s.png)
SpringMVC执行过程详细讲解
![](https://img.aspxhome.com/file/2023/9/62359_0s.png)
如何使用Jenkins构建GIT+Maven项目
![](https://img.aspxhome.com/file/2023/9/61839_0s.png)
Android使用PhotoView实现图片双击放大单击退出效果
C#如何绑定多个按钮到同一个事件
Java案例使用比较排序器comparator实现成绩排序
java io文件操作从文件读取数据的六种方法
![](https://img.aspxhome.com/file/2023/5/77375_0s.jpg)
Java任意长度byte数组转换为int数组的方法
快速学习六大排序算法
![](https://img.aspxhome.com/file/2023/5/105175_0s.gif)
Android Build Variants 为项目设置变种版本的方法
![](https://img.aspxhome.com/file/2023/1/89541_0s.jpg)
Sharding-Proxy基本功能用法介绍
![](https://img.aspxhome.com/file/2023/7/69877_0s.jpg)
浅谈Java并发中的内存模型
![](https://img.aspxhome.com/file/2023/3/62093_0s.png)
Java 在PDF中添加条形码的两种方法
![](https://img.aspxhome.com/file/2023/0/80930_0s.png)
Android GestureDetector手势滑动使用实例讲解
![](https://img.aspxhome.com/file/2023/4/88704_0s.jpg)
Java花式解决'分割回文串 ii'问题详解
![](https://img.aspxhome.com/file/2023/3/83593_0s.jpg)
Java集合Map的clear与new Map区别详解
![](https://img.aspxhome.com/file/2023/1/63321_0s.png)
MyBatis动态SQL如何实现前端指定返回字段
浅析Java自定义注解的用法
![](https://img.aspxhome.com/file/2023/7/84167_0s.png)