浅谈面试中的递归算法

如你所知，许多公司的面试中都会或多或少涉及到一些算法相关的概念，有的只需要吹吹牛即可，有的则会递给你一张纸让你手撕一个 xx 算法，对于相关算法有很多的分类，本文将一些面试中可能会用到的递归算法进行整理，先收藏着，说不定什么时候就用到了。

递归，在程序语言中简单的理解是：方法自己调用自己。

对于递归的程序，有两个要求：

1. 子问题需与原始问题为同样的事，且更为简单；
2. 不能无限制地调用本身，需有个出口，化简为非递归状况处理。

举例，对于一个 1+2+3+...+100 的程序，如果用循环写的话，程序如下：

int sum = 0;
for (int i = 1; i <= 100; i++) {sum = sum + i;
}
cout << "Sum is: " << sum;

用递归的写法则是如下：

int sum(int n)
{if (n == 1) {return 1; // 这个就是递归的出口，化简为非递归状况处理} else {return sum(n - 1) + n; // 子问题须与原始问题}
}

理解了递归的基本写法和定义之后，我们就可以学习一下面试中常见的一些递归算法了。这个后面我们再来细讲。