初识递归算法

本文由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\times1=1205!=5×4×3×2×1=120。
假设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(x=1) \\ &x\times f(x-1)\space(x>1) \\ \end{aligned} \right.f(x)={​1(x=1)x×f(x−1)(x>1)​

翻译为代​码如下。

Python

deff(x):ifx>1:returnx*f(x-1)return1

C++

longlongintf(x){if(x>1){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 22，f(3)返回6…直到f ( 5 ) f(5)f(5)返回120 120120。
递归本质上是一种由系统自动维护的栈，数据先进后出（FILO，First in Last out）。
可见，第一个进去的f ( 3 ) f(3)f(3)最后一个出来，而最后进去的f ( 1 ) f(1)f(1)第一个出来。

优缺点分析

递归的写法有许多好处。首先，递归的代​码简洁，可以用较少的代​码表达较复杂的过程。其次，递归的效率还很高。

但递归不是万能的。能写成递归形式的算法，基本都可以写成非递归。且一个算法是否该用递归，还需要考虑数据规模。如果数据规模太过巨大，可能会导致递归几百万层，最终爆栈。

不过话说回来，递归最深深度也取决于硬件、操作系统、编程语言等因素，一般来说递归个几万层没多大问题。

递归还有一个小缺点：代​码太过简洁，可能难以理解，对初学者来说可能不太友好。

题目

有的题目用到了递归​算法：
洛谷 P1087 [NOIP2004 普及组] FBI 树
洛谷 P1010 [NOIP1998 普及组] 幂次方

结尾

好啦，今天的分享到此结束，记得点赞+收藏哦！