递归type
status
date
slug
summary
tags
category
icon
password
Property
递归（Recursion），在数学和计算机科学中是指在函数的定义中使用函数自身的方法，在计算机科学中还额外指一种通过重复将问题分解为同类的子问题而解决问题的方法
基本思想：某个函数直接或者间接地调用自身，这样原问题的求解就转换为了许多性质相同但是规模更小的子问题。求解时只需要关注如何把原问题划分成符合条件的子问题，而不需要过分关注这个子问题是如何被解决的。
递归代码最重要的两个特征：结束条件和自我调用。自我调用是在解决子问题，而结束条件定义了最简子问题的答案。
比如阶乘的计算方法在数学上的定义为：
可以使用调用函数自身的方式来实现阶乘函数
fact(n)：以
n = 6为例，上述代码中阶乘函数 fact(6)的计算过程如下：可以把阶乘函数的递归计算过程分为两个部分：
- 先逐层向下调用自身，直到达到结束条件（即
n == 0）。
- 然后再向上逐层返回结果，直到返回原问题的解（即返回
fact(6) == 720）。
这两个部分也可以叫做「递推过程」和「回归过程」：
- 递推过程：指的是将原问题一层一层地分解为与原问题形式相同、规模更小的子问题，直到达到结束条件时停止，此时返回最底层子问题的解。
- 回归过程：指的是从最底层子问题的解开始，逆向逐一回归，最终达到递推开始时的原问题，返回原问题的解。
递归的注意点
- 避免栈溢出
在程序执行中，递归是利用堆栈来实现的。每一次递推都需要一个栈空间来保存调用记录，每当进入一次函数调用，栈空间就会加一层栈帧。每一次回归，栈空间就会减一层栈帧。由于系统中的栈空间大小不是无限的，所以，如果递归调用的次数过多，会导致栈空间溢出。
为了避免栈溢出，可以在代码中限制递归调用的最大深度来解决问题。当递归调用超过一定深度时（比如 100）之后，不再进行递归，而是直接返回报错。
当然这种做法并不能完全避免栈溢出，也无法完全解决问题，因为系统允许的最大递归深度跟当前剩余的占空间有关，事先无法计算。如果使用递归算法实在无法解决问题，可以考虑将递归算法变为非递归算法（即递推算法）来解决栈溢出的问题。
- 避免重复运算
在使用递归算法时，还可能会出现重复运算的问题。比如斐波那契数列的定义是：
对应的递归过程：
为了避免重复计算，可以使用一个缓存（哈希表、集合或数组）来保存已经求解过的的结果，这也是动态规划算法中的做法。当递归调用用到时，先查看一下之前是否已经计算过结果，如果已经计算过，则直接从缓存中取值返回，而不用再递推下去，这样就避免了重复计算问题。
斐波那契数
题目：通常用
F(n)表示形成的序列称为 斐波那契数列 。该数列由 0和 1开始，后面的每一项数字都是前面两项数字的和。给定 n，计算 F(n)。递归算法:
圆圈中最后剩下的数字
题目： 这个数字排成一个圆圈，从数字开始，每次从这个圆圈里删除第个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。例如， 这5个数字组成一个圆圈，从数字开始每次删除第个数字，则删除的前4个数字依次是，因此最后剩下的数字是。
示例 1：
在不考虑溢出的情况下，