目录介绍例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 普及组] 幂次方结尾好啦今天的分享到此结束记得点赞收藏哦
