递归经典例子

你的名字 2022-08-09 12:52 203阅读 0赞

程序调用自身的编程技巧称为递归（ recursion）。 一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。 一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。 注意： (1) 递归就是在过程或函数里调用自身; (2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口，否则将无限进行下去（死锁）。 递归算法一般用于解决三类问题： (1)数据的定义是按递归定义的。(Fibonacci函数) (2)问题解法按递归算法实现。(回溯) (3)数据的结构形式是按递归定义的。(树的遍历，图的搜索) 递归的缺点： 递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。 例一 1、 古典问题——有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问第三年每个月的兔子总数为多少？（提示：兔子的规律为数列1,1,2,3,5,8,13,21....） 代码： class Program \{ static void Main(string\[\] args) \{ Program p = new Program(); Console.WriteLine(p.tuzi(7)); \} public int tuzi(int n) \{ if (n == 1 || n == 2) \{ return 1; \} else \{ return tuzi(n - 1) + tuzi(n - 2); \} \} \} 例二 2、 趣味问题——年龄。有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后问第一个人，他说是10岁。请问第五个人多大？用递归算法实现。 代码： class Program \{ static void Main(string\[\] args) \{ Program p = new Program(); Console.WriteLine( p.age(5)); \} ///  /// 递归法求岁数 /// /// 有几个人 /// int age(int n) \{ int c; if(n==1) return 10; else \{ c = age(n-1)+2; return c; \} \} 例三 3、 趣味问题——猴子吃桃。海滩上有一堆桃子，五只猴子来分。第一只猴子把这堆桃子凭据分为五份，多了一个，这只猴子把多的一个扔入海中，拿走了一份。第二只猴子把剩下的桃子又平均分成五份，又多了一个，它同样把多的一个扔入海中，拿走了一份，第三、第四、第五只猴子都是这样做的，问海滩上原来最少有多少个桃子？ 代码： class Program \{ static void Main(string\[\] args) \{ Program p = new Program(); Console.WriteLine( p.PeachNumber(5)); \} ///  /// 递归法求桃子数 /// /// /// int PeachNumber(int n) \{ if (n == 1) \{ //最后一个是至少是六个 return 6; \} else \{ return (PeachNumber(n - 1) + 1) \* 5; \} \} 例四 汉诺塔问题。汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。用C\#编写一个程序，实现输出三个圆盘的汉诺塔移动步骤 static void Main(string\[\] args) \{ int li\_disk\_total; System.Console.Write("Please input disk total:"); int.TryParse(System.Console.ReadLine(),out li\_disk\_total); hanoi(li\_disk\_total, 'a', 'b', 'c'); System.Console.WriteLine("Move success"); System.Console.ReadLine(); \} public static void hanoi(int n,char a,char b,char c) \{ if (n == 1) move(n, a, c); else \{ hanoi(n - 1, a, c, b); move(n, a, c); hanoi(n - 1, b, a, c); \} \} public static void move(int n,char x,char y) \{ System.Console.WriteLine("Disk " + n.ToString() + " from " + x + " move to " + y); \}