初识递归算法

目录介绍例PythonC原理优缺点分析题目结尾本文由Jzwalliser原创发布在CSDN平台上遵循CC 4.0 BY-SA协议。因此若需转载/引用本文请注明作者并附原文链接且禁止删除/修改本段文字。违者必究谢谢配合。个人主页blog.csdn.net/jzwalliser介绍递归是一种算法即自己调用自己。可以是一个函​数自己调用自己即直接递归也可以是两个函​数相互调用即间接递归。递归​算法主要由两个部分组成递归操作及递归边​界。递归操作是函​数的主体部分负责执行运算、实现功能递归边​界即一个条件 满足条件后停止递归并返回上一层以避免程​序无​限递归下去而陷入死循环。例比如计算阶​乘就可以使用递归​算法来实现。n ! n × ( n − 1 ) × ( n − 2 ) × ⋯ × 2 × 1 n!n\times(n-1)\times(n-2)\times\cdots\times2\times1n!n×(n−1)×(n−2)×⋯×2×1例如5 ! 5 × 4 × 3 × 2 × 1 120 5!5\times4\times3\times2\times11205!5×4×3×2×1120。假设x xx的阶​乘用f ( x ) f(x)f(x)来表示x ∈ Z x\in\mathbb{Z_}x∈Z​那么f ( x ) { 1 ( x 1 ) x × f ( x − 1 ) ( x 1 ) f(x)\left\{ \begin{aligned} 1\space(x1) \\ x\times f(x-1)\space(x1) \\ \end{aligned} \right.f(x){​1(x1)x×f(x−1)(x1)​翻译为代​码如下。Pythondeff(x):ifx1:returnx*f(x-1)return1Clonglongintf(x){if(x1){returnx*f(x-1);}return1;}原理可以发现当调用f ( 5 ) f(5)f(5)时程​序就会递归调用f ( 4 ) f(4)f(4)并计算5 × f ( 4 ) 5\times f(4)5×f(4)然后再计算4 × f ( 3 ) 4\times f(3)4×f(3)…直到调用f ( 1 ) f(1)f(1)才终于撞到了边​界条件停止递归并返回1 11接着f ( 2 ) f(2)f(2)返回2 22f(3)返回6…直到f ( 5 ) f(5)f(5)返回120 120120。递归本质上是一种由系统自动维护的栈数据先进后出FILOFirst in Last out。可见第一个进去的f ( 3 ) f(3)f(3)最后一个出来而最后进去的f ( 1 ) f(1)f(1)第一个出来。优缺点分析递归的写法有许多好处。首先递归的代​码简洁可以用较少的代​码表达较复杂的过程。其次递归的效率还很高。但递归不是万能的。能写成递归形式的算法基本都可以写成非递归。且一个算法是否该用递归还需要考虑数据规模。如果数据规模太过巨大可能会导致递归几百万层最终爆栈。不过话说回来递归最深深度也取决于硬件、操作系统、编程语言等因素一般来说递归个几万层没多大问题。递归还有一个小缺点代​码太过简洁可能难以理解对初学者来说可能不太友好。题目有的题目用到了递归​算法洛谷 P1087 [NOIP2004 普及组] FBI 树洛谷 P1010 [NOIP1998 普及组] 幂次方结尾好啦今天的分享到此结束记得点赞收藏哦