这个系列主要是为了介绍算法，众所周知，算法是一个程序的灵魂，也是程序中最重要的东西。一个优秀的算法可以大幅度减少程序的所用的时间和所占的空间。这个系列将介绍一些常用算法和一些习题。这些习题来自leetcode。下面开始介绍这个系列的第一个算法：递归。
梦开始的地方—斐波那契数列
我们都知道斐波那契数列,第一项为0，第二项为1，第三项为1（0+1),第四项为2（1+1）…
从这个数列我们可以看出除了第一项和第二项，每一项都是前两项之和。我们知道两项就可以知道下一项。但我们无法快速得出第几项是什么数。但是我们拥有计算机这样的的拥有超强计算能力的机器，我们现在可以很容易的得出答案。现在我们来利用代码来解决这个问题。
int Fibonacci(int n) {
if (n == 1)
{
return 0;
}
if (n == 2)
{
return 1;
}
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
从上述代码我们可以看出求斐波那契数列的某一项是求前面两项，持续调用本身来求，一直到第一项和第二项，由于第一和第二项是我们直接规定的0和1。这样我们就可以来求任何一项的数了。求斐波那契数列中任何一项虽然是很简单，但是折射出一个算法思想：递归。
什么是递归
从上面斐波那契数列我们可以看出得出思路，第一：重复调用本身。第二：具有边界条件。
这样我们就可以看出递归的特点。现给出递归的定义：一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
从上述我们可以看出递归具有显著特点：
- 子问题须与原始问题为同样的事，且更为简单
- 不能无限制地调用本身，须有个出口，化简为非递归状况处理
简单来说递归就是重复调用自己
递归与迭代
递归，是重复调用自己。这一特点很容易让我们想起再编写代码中常用的结构：迭代。
首先介绍一下迭代的概念：迭代是重复反馈过程的活动，每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。从上述介绍我们可以看出：迭代与递归的一个区别：递归在计算机科学中，指的是在函数定义中使用函数自身的方法（A 使用A）;迭代 每迭代一次的结果作为下一次的初始值（A使用B）。而从结构来看：递归是一个树结构，而迭代是一个闭环。
递归问题
下面我们来借助几道题来看看递归。
# 题目描述：递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。
======================================================================
code：
class Solution:
def support(self,A:int,B:int)->int:
if A==1:
return B
else:
return self.multiply(A-1,B)+B
def multiply(self, A: int, B: int) -> int:
if A==0 or B==0:
return 0
if A>B:
A,B=B,A
ans=self.support(A,B)
return ans本题写了一个support函数来完成乘法，本题思路利用乘法可以用加法来表现。为了减少递归次数，我们需要把小的数逐次减一，把B逐次相加。
# 题目：第K个语法符号
# 题目描述：在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。
给定行数 N 和序数 K，返回第 N 行中第 K个字符。（K从1开始）
=======================================================================
class Solution(object):
def GetAnswer(self, N, K):
if N == 1: return 0
return (1 - K%2) ^ self.GetAnswer(N-1, (K+1)/2)从题目描述我们可以得出
0
01
0110
01101001
…………………………….
我们可以看出除了第一行以外的每一行数字都可以从上一行的数字得出。所以我们可以使用递归的方法来得出我们想要的数字。据此可以总结出规律，第 K 个数字是上一行第 (K+1) / 2 个数字生成的。如果上一行的数字为 0，被生成的数字为 1 - (K%2)，如果上一行的数字为 1，被生成的数字为 K%2。
总结
递归是一个简单，方便的思想。当我们找到边界条件和可以重复调用本身的时候，就可以使用递归的方法。但是我们使用递归算法，递归会浪费较多时间（由于是函数调用自身，而函数调用是有时间和空间的消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址以及临时变量，而往栈中压入数据和弹出数据都需要时间），所以我们谨慎使用递归算法。