专栏首页bigsai从阶乘、斐波那契、汉诺塔剖析彻底搞懂递归算法

从阶乘、斐波那契、汉诺塔剖析彻底搞懂递归算法

目录

  • 递归介绍
  • 递归求阶乘
  • 递归求斐波那契
  • 递归解决汉诺塔
  • 总结

递归介绍

递归:就是函数自己调用自己。子问题须与原始问题为同样的事,或者更为简单; 递归通常可以简单的处理子问题,但是不一定是最好的。

对于递归要分清以下概念:

  • 自己调用自己
  • 递归通常不在意具体操作,只关心初始条件上下层的变化关系
  • 递归函数需要有临界停止点,即递归不能无限制的执行下去。通常这个点为必须经过的一个数。
  • 递归通常能被其他方案替代(栈、数组正向求)。

认识递归,递归函数通常简易但是对于初学者可能很难取理解它。拿一个递归函数来说。

static void digui()
{
	System.out.println("bigsai前");
	digui();
	System.out.println("bigsai后");
}

是一个递归吧? 不是正常递归没有结束条件,自己一致调用自己死循环。 那正确的递归应该这样

static void digui(int time)
{
	if(time==0) {}//time==0不执行
	else {
		System.out.println("bigsai前time: "+time);
		digui(time-1);
		System.out.println("bigsai后time: "+time);	
	}	
}

对于这样一种递归,它的执行流程大致是这样的

所以,调用dugui(5)在控制台输出是这样的

那么,我想你对递归函数执行的流程应该有所了解了吧。

递归求阶乘

n!=n*(n-1)*-----*1=n!=n*(n-1) 所以阶乘的上下级的关系很容易找到。我们假设一个函数jiecheng(n)为求阶乘的函数。 这个阶乘,你可以这样命名:

int jiecheng(int n)
{
   int va=1;
   for(int i=n;i>0;i--)
   {
       va*=i;
   }
   return i;
}

但是你还可以简便这样:

static int jiecheng(int n)
{
	if(n==0)//0的阶乘为1
	{
		return 1;
	}
	else {
		return n*jiecheng(n-1);//return n*(n-1)*jiecheng(n-2)=-------
	}
}

运行流程为这样

递归求斐波那契

按照上述思想,我们假设求斐波那契设成F(n); 首先,斐波那契的公式为:

  • F[n]=F[n-1]+F[n-2](n>=3,F[1]=1,F[2]=1)
  • 也就是除了n=1和2特殊以外,其他均是可以使用递推式。

那么递推实现的代码为:

static long F(int n)
{
	if(n==1||n==2) {return 1;}
	else {
		return F(n-1)+F(n-2);
	}
}

其实它的调用流程为:

当然,其效率虽然不高,可以打表优化,后面可能还会介绍矩阵快速幂优化!

递归解决汉诺塔

汉诺塔是经典递归问题:

相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。

  1. 如果A只有一个(A->C)
  2. 如果A有两个(A->B),(A->C),(B->C)
  3. 如果A有三个(A->C),(A->B),(C->B),(A->C),(B->A),(B->C),(A->C).
  4. 如果更多,那么将会爆炸式增长。

可以发现每增加一步,其中的步骤会多很多。但是不妨这样想:

  • 当有1个要从A->C时,且已知移动方式。使用函数表示move(a->c)。同理其他move操作。
  • -------省略中间若干步骤不看,用递归思想看问题

分析:n个从a—>cn-1个a—>c有什么联系?(hannuo(n)—>hannuo(n-1)有啥关系) 假设有n个盘子

  • hannuo(n-1)之后n-1个盘子从A—>C.
  • 此时剩下底下最大的,只能移动到B,move(A,B)
  • 那么你是否发现什么眉目了,只需原先的huannuo(n-1)相同操作从C—>B即可完成转移到B;那么我们的之前函数应该写成hannuo(n-1,A,C)但是又用到B,所以把B传进来hannuo(n-1,A,B,C)先表示为从n-1个从A(借助B执行若干操作)转到C。
  • 这一系列操作使得将n个盘子从A—>B但是我们要的是A—>C才是需要的hannuo(n,A,B,C);那么我们只需要更改下hannuo(n-1,----)顺序就好啦!

经过上面分析,那么完整的操作为:

package 递归;
public class hannuota {
	static void move(char a,char b)
	{
		System.out.println("移动最上层的"+ a+ "到"+ b+ "\t");
	}
	static void hannuota(int n,char a,char b,char c)//主要分析每一大步对于下一步需要走的。
	{
		if(n==1) {move(a,c);}//从a移到c
		else
		{
			hannuota(n-1,a,c,b);//将n-1个从a借助c移到b
			move(a,c); //将第n(最后一个)从a移到c。
			hannuota(n-1,b,a,c);//再将n-1个从b借助a移到c
		}
	}
	public static void main(String[] args)
	{
		
		hannuota(5,'a','b','c');
	}
}

总结

其实递归在某些场景的效率是很低下的。尤其是斐波那契.从图你就可以发现一个简单的操作有多次重复。因为它的递归调用俩个自己.那么它的递归的膨胀率是指数级别的,重复了大量相同计算。当然这种问题也有优化方案的:

  • 从前往后打表计算,采用类似动态规划的思想。从前往后考虑。比如斐波那契F[n]=F[n-1]+F[n-2];那么我用数组储存。从第三项开始F[3]=F[2]+F[1](均已知),再F[4]=F[3]+F[2]-----这样,时间复杂度是O(N),线性的。
  • 当然,对于阶乘那种递归虽然时间是没有减少,但是如果需要多次访问一个阶乘,那么可以采用同样思想(打表)解决问题。

本文分享自微信公众号 - bigsai(bigsai),作者:bigsai

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-08-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 短小精悍的多源最短路径算法—Floyd算法

    在图论中,在寻路最短路径中除了Dijkstra算法以外,还有Floyd算法也是非常经典,然而两种算法还是有区别的,Floyd主要计算多源最短路径。

    bigsai
  • 再送10张关于算法的GIF 动图给你,记得查收

    今天为大家整理了十张动图GIFS,有助于认识循环、递归、二分检索等概念的具体运行情况。

    bigsai
  • csdn账号密码登录剖析(模拟登录)

    可以根据上图分析得知:有uaToken 和webUmidToken两个token。 分析参数肯定是要打断点的,一般有直接搜索,查看js调用堆栈,和hook查找找...

    bigsai
  • 算法导论第四章分治策略剖根问底(二)

       在上一篇中,通过一个求连续子数组的最大和的例子讲解,想必我们已经大概了然了分治策略和递归式的含义,可能会比较模糊,知道但不能用语言清晰地描述出来。但没关系...

    CloudDeveloper
  • 超全递归技巧整理,这次一起拿下递归

    大家好,我是多选参数的程序锅,一个正在 neng 操作系统、学数据结构和算法以及 Java 的硬核菜鸡。本篇将主要介绍递归相关的内容,下面是本篇的内容提纲。

    syy
  • Python之路_递归

    py3study
  • 什么是递归--What does resursion mean?

    在Google.com.hk或者在Google.com上搜索 递归或者recursion 发现Google“抽了”,明明搜索正确,为啥还显示一个查询错误的提示?...

    Fisherman渔夫
  • Python数据结构与算法笔记(3)

    递归是一种解决问题的方法,将问题分解为更小的子问题,直到得到一个足够小的问题可以被很简单地解决,通常递归设计函数调用自身。递归允许我们编写优雅的解决方案,解决可...

  • 什么是递归?

    一上来你肯定觉得读这句话好绕,好吃力。 其实你用递归来读就很简单了: 递归要有一个终点(小鲤鱼) 当递归尚未达到终点的时候,函数会反复调用自己。 ...

    阿珏
  • 读书笔记:《算法图解》第三章 递归

    孙亖

扫码关注云+社区

领取腾讯云代金券