美高梅官方网站3045-mgm6608美高梅app下载
递归实现标准

递归实现标准

作者:mgm6608美高梅app下载    来源:未知    发布时间:2020-01-19 08:39    浏览量:

级别:★☆☆☆☆标签:「递归」「四条递归实现基本原则」作者: 陈彬审校: QiShare团队

引言:这篇文章主要讲述递归实现原则。为了方便理解,每个原则都会对应的段代码实例。

最近在系统学习数据结构与算法,初学编程时以练手题的形式见过斐波那契数列,当时仅仅是从「语法」角度进行理解,如今再次见到,从「算法」角度再次思考,多了一层理解。

 

 一 、递归算法简介

在数学与计算机科学中,递归是指在函数的定义中使用函数自身的方法。
  递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。
递归算法解决问题的特点:
  (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)个数的和。用递归算法实现如下:

图片 1

 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

 

2、阶乘 

还有就是求一个数的阶乘,也会用到递归,这个比较简单,直接给出实现代码,如图:

图片 3

 

 三 、汉诺塔问题

 汉诺塔是根据一个传说形成的数学问题:

图片 4

        汉诺塔示意图(图片来自网络)

 有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:
  1、每次只能移动一个圆盘;
  2、大盘不能叠在小盘上面。
  提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须遵循上述两条规则。
  问:如何移?最少要移动多少次?

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

图片 5

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);
         }
      }

图片 6

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

图片 7

 

 四 、排列组合

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

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

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

图片 8

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();
         }
      }

图片 9

调用代码如下:

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

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

图片 10

 

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

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

图片 11

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

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

图片 12

 此时声明全局变量,如下:

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

这个时候,我们修改Permutation方法,如下:

图片 13

  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);
         }
      }

图片 14

这样,我们执行了Permutation方法后,就将结果保存到链表中了。用的时候,我们只要遍历NodeList就可以了。如图:

图片 15

 递归算法就先说到这里了。谈到算法,就必需提数据结构,看来真的要“学到老了”~~

 

 作者:大城小梦

QQ交流群:51499554

 博客地址:

 声明:本博客原创文字只代表本人工作中在某一时间内总结的观点或结论,与本人所在单位没有直接利益关系。非商业,未授权,贴子请以现状保留,转载时必须保留此段声明,且在文章页面明显位置给出原文连接。

如果大家感觉我的博文对大家有帮助,请推荐支持一把,给我写作的动力。

 

 

一、定义:

目前我查到的资料中关于递归解释有两种:

  • 程序调用自身的编程技巧称为递归。(源于知识丰厚的度娘)
  • 当一个函数用它自己来定义时就称为是递归。(源于数据结构与算法分析书籍)

第一种说法比较直接的描述了递归在程序的实现,具体实现见下面实现原则暂不赘述,而第二种说法偏向于算法,利用数学知识更方便理解,如函数F=2F+X


二、四条实现基本原则:

斐波那契数列

指的是这样一个数列:1、1、2、3、5、8、13、21、……在数学上,斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=Fn-1+Fn-2(n>=2,n∈N*)。
用文字来说,就是斐波那契数列列由 0 和 1 开始,之后的斐波那契数列系数就由之前的两数相加。 --《百度百科》

下一篇:没有了
友情链接: 网站地图
Copyright © 2015-2019 http://www.zen-40.com. mgm美高梅有限公司 版权所有