经典实例讲解C#递归算法
一 、递归算法简介
在数学与计算机科学中,递归是指在函数的定义中使用函数自身的方法。
递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。
递归算法解决问题的特点:
(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就可以了。如图:
递归算法就先说到这里了。谈到算法,就必需提数据结构,看来真的要“学到老了”~~
以上就是经典实例讲解C#递归算法的详细内容,更多关于c#递归算法的资料请关注猪先飞其它相关文章!
相关文章
- 我们在使用C#做项目的时候,基本上都需要制作登录界面,那么今天我们就来一步步看看,如果简单的实现登录界面呢,本文给出2个例子,由简入难,希望大家能够喜欢。...2020-06-25
- 这篇文章主要介绍了C# 字段和属性的的相关资料,文中示例代码非常详细,供大家参考和学习,感兴趣的朋友可以了解下...2020-11-03
- 这篇文章主要介绍了C#中截取字符串的的基本方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-11-03
- 这篇文章主要介绍了C#实现简单的Http请求的方法,以实例形式较为详细的分析了C#实现Http请求的具体方法,需要的朋友可以参考下...2020-06-25
- 本文给大家分享C#连接SQL数据库和查询数据功能的操作技巧,本文通过图文并茂的形式给大家介绍的非常详细,需要的朋友参考下吧...2021-05-17
- 本文主要介绍了C#中new的几种用法,具有很好的参考价值,下面跟着小编一起来看下吧...2020-06-25
使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序)
这篇文章主要介绍了使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序),小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25- 这篇文章主要介绍了C#开发Windows窗体应用程序的简单操作步骤,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-04-12
- 这篇文章主要介绍了C#从数据库读取图片并保存的方法,帮助大家更好的理解和使用c#,感兴趣的朋友可以了解下...2021-01-16
- 作者:Sabine 【导读】本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System; namespace BubbleSorter { public class Bubb...2020-06-25
- 最近做一个小项目不可避免的需要前端脚本与后台进行交互。由于是在asp.net中实现,故问题演化成asp.net中jiavascript与后台c#如何进行交互。...2020-06-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 轻松学习C#的基础入门,了解C#最基本的知识点,C#是一种简洁的,类型安全的一种完全面向对象的开发语言,是Microsoft专门基于.NET Framework平台开发的而量身定做的高级程序设计语言,需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C#变量命名规则小结,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-09-09
- 这篇文章主要介绍了C#绘制曲线图的方法,以完整实例形式较为详细的分析了C#进行曲线绘制的具体步骤与相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C# 中取绝对值的函数。具有很好的参考价值。下面跟着小编一起来看下吧...2020-06-25
- 这篇文章主要介绍了c#自带缓存使用方法,包括获取数据缓存、设置数据缓存、移除指定数据缓存等方法,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了c#中(&&,||)与(&,|)的区别详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 下面小编就为大家带来一篇C#学习笔记- 随机函数Random()的用法详解。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25