Menu

递归–递归的用法

2018年2月6日 - 算法,数据结构

递归是指在函数的定义中使用函数自身的方法。
递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。
递归算法解决问题的特点:
(1) 递归就是在过程或函数里调用自身。
(2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。
(3) 递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。在实际编程中尤其要注意栈溢出问题。

借助递归方法,我们可以把一个相对复杂的问题转化为一个与原问题相似的规模较小的问题来求解,递归方法只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。但在带来便捷的同时,也会有一些缺点,也即:通常用递归方法的运行效率不高。

 

常用递归解决的问题,快速排序会使用到递归算法,汉诺塔问题,排列组合问题

 

1.汉诺塔问题

递归,

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace suanfarui
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            HanoiCalculator c = new HanoiCalculator();
            Console.WriteLine(c.CalculateHanoi(3));//打印结果

        }
    }
    class HanoiCalculator
    {
        public int CalculateHanoi(int count)//盘子数量
        {
            int stepForOnlyCurrentDish = 1;
            if(count==1)
            {
                return stepForOnlyCurrentDish = 1;

            }
            //int totalSteps = stepForOnlyCurrentDish + CalculateHanoi(count – 1) * 2;
            int totalSteps = stepForOnlyCurrentDish + CalculateHanoi(count – 1) + CalculateHanoi(count – 1);//totalSteps移动步数
            return totalSteps;

        }
    }

}

2.斐波那契数列

 

3.排列组合

 

4快速排序也会用到递归

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

%d 博主赞过: