记得我春招美团第三轮主管面试的时候被问到递归题。总结下来一般第三轮总管面试很喜欢出一些非常规的题目来考验大家。当时自己很慌，其实对递归不是很深入的了解。所以没有面试成功，也与美团失之交臂。其实我们程序员最经典的算法就是递归，所以建议大家还是很认真的去对待一下。以下我总结了面试中常被问到的递归题，大家认真看懂之后应该能够应付面试中的问题。
1.序
递归是计算机科学中的一个重要概念。它是许多其他算法和数据结构的基础。然而，对于许多初学者来说，掌握它可能是一件非常棘手的事情。
实现调用自身的函数的诀窍在于，每当递归函数调用自身时，它都会将给定的问题拆解为子问题。递归调用继续进行，直到到子问题无需进一步递归就可以解决的地步。
为了确保递归函数不会导致无限循环，它应具有以下属性：
1一个简单的基本案例（basic case）（或一些案例） —— 能够不使用递归来产生答案的终止方案。
2一组规则，也称作递推关系（recurrence relation），可将所有其他情况拆分到基本案例。
注意，函数可能会有多个位置进行自我调用。
【摘要】 递归具有很多的优点，它可以将一个大的问题划分为小的子问题，然后再逐步细分，达到解决问题的目的。递归的实现借用了栈桢的建立和销毁，所以它是很方便的。但是递归也有一些缺点，比如说，如果递归调用太深，栈桢消耗过大，就会出现栈溢出的问题，因此，在我们使用递归之前，应该仔细考虑适不适合使用递归来解决这个问题。同时，递归深度太深，也会使得运算时间大大增加，所以递归的结论一般都是在理论的基础上的。
递归算法的时间复杂度：递归的总次数*每次递归的数量。
递归算法的空间复杂度：递归的深度*每次递归创建变量的个数。
2.题目
2.1 吃苹果问题
每天吃三分之一再加一个，到最后一天只有一个。
public static void main(String[] args) {
System.out.println(getNum(3));
}
static int dp = 0;
public static int getNum(int n) {
if (n == 1) {
return 1;
}
dp = 1 + getNum(n - (n / 3 + 1));
return dp;
}
2.2 数组中最大值
tatic int res = Integer.MIN_VALUE;
public static int getMax(int[] nums, int n) {
if (n == 0) {
return res;
}
res = Math.max(nums[n], getMax(nums, n - 1));
return res;
}
2.3用递归调用的方法求n!
public class Test23 {
public static void main(String[] args) {
System.out.println(fo(5));
}
public static int fo(int n){
if(n<2){
return 1;
}else{
return n*fo(n-1);
}
}
}
2.4 用递归法求和1+2+3+4…+n
public class Test23 {
public static void main(String[] args) {
System.out.println(add(5));
}
public static int add(int m){
if(m < 2){
return 1;
}else{
return m+add(m-1);
}
}
}
2.5一列数的规则如下: 1、1、2、3、5、8、13、21、34… 求第30位数是多少， 用递归算法实现。
public class Test23
public static void main(String[] args) {
System.out.println(find(7));
}
public static int find(int n){
if (n <= 0){
return 0;
} else if(n > 0 && n <= 2){
return 1;
}
return find(n-1)+find(n-2);
}
}
2.6将一整数逆序后放入一数组中（要求递归实现） Ex : 1234 变为 {4,3,2,1}
public class Test23 {
public static void main(String[] args) {
int[] res = new int[4];
revert(res,0,1234);
System.out.println(Arrays.toString(res));
}
static int revert(int rs[], int i, int number) {
if (i < rs.length) {
rs[i] = number % 10;
number = (number - number % 10) / 10;
return revert(rs, i + 1, number);
} else {
return 0;
}
}
}
2.7递归实现回文判断（如：abcdedbca就是回文，判断一个面试者对递归理解的简单程序）
public class Test23 {
public static void main(String[] args) {
int[] res = new int[4];
String str = "abcba";
//"abcdedbca"
System.out.println(loopWord(str,0));
}
static boolean loopWord(String str, int i) {
if (str.charAt(i) == str.charAt(str.length() - 1 - i)) {
if (i == (str.length() + 1) / 2) {
return true;
}
return loopWord(str, i + 1);
} else {
return false;
}
}
}
2.8分解成质因数(如435234=251171732 华为笔试题)
public class Test23 {
public static void main(String[] args) {
int[] res = new int[4];
String str = "abcba";
//"abcdedbca"
dividePrimeToFactors(435234, 2);
}
static int dividePrimeToFactors(int num, int factor) {
while ((factor < num) && (num % factor != 0)) {
factor++;
}
System.out.print(factor + " ");
num = num / factor;
if (factor >= num) {
return factor;
}
return dividePrimeToFactors(num, factor + 1);
}
}
2.9喝啤酒问题
public class Test23 {
public static void main(String[] args) {
System.out.println(help(8));
}
public static int sum = 0;
public static int help(int money){
int count = (int) Math.floor(money/2);
//喝几瓶
int curPing = count;
//空瓶数
int curGai = count;
//瓶盖数
helper(count,curPing,curGai);
return sum;
}
public static void helper(int count,int curPing,int curGai){
if(curPing<2&&curGai<4){
//递归终结条件
sum = count;
return;
}
if(curGai>=4){
int curAdd1 = (int) Math.floor(curGai/4);
count+=curAdd1;
//增加的瓶子数
curGai=curAdd1+curGai%4;
//增加的瓶数＋剩余于的瓶盖；
curPing+=curAdd1;
}
if(curPing>=2){
int curAdd2 = (int) Math.floor(curPing/2);
count+=curAdd2;
curPing=curAdd2+curPing%2;
//增加的瓶数＋剩余于空瓶；
curGai+=curAdd2;
}
helper(count,curPing,curGai);
}
}
2.10递归乘法
写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。
public int multiply(int A, int B) {
if(A==0||B==0){
return 0;
}
if(B==1){
return A;
}
return A+multiply(A,B-1);
}
2.11递归法求斐波那契数列
在这里我先要说的是，递归法求菲波那切数列并不是一个很好的解决办法，如果你要问我为什么，其实前面也提到了，如果求第10个或者第20数的值，还好，但是如果要求第100个呢？这样做消耗的栈桢将会是很大的，我先拿一张图来大概表示一下栈桢的消耗过程
并且，随着递归次数越多，时间复杂度也会越高，综合这两点，我觉得用循环来代替递归是很明智的选择。当然我也不是就说递归不好了，有时候用递归解决问题还是相当给力的。
菲波那切数列求值，思想就是每一个值都是前面两个数的和，因此放到递归里面就可以分解为子问题，求前两个数字的结果，就这样一直往前走，直到遇到1就返回，然后再把值一个个相加，得到最后的结果。
int fabonaci(int i)
{
if(i<=0)
return 0;
else if(i==1 ||i==2)
return 1;
else
return(fabonaci(i-1)+fabonaci(i-2));
}
时间复杂度分析
当n=5时，在递归调用过程中，Fibonacci(3)被计算了2次，Fibonacci(2)被计算了3次，Fibonacci(1)被计算了5次，Fibonacci(0)被计算了3次。
可见递归出口在n>=2是，就会一直在现有函数栈上开辟新的空间，所以容易出现栈溢出。
二叉树的高度为n-1,一个高度为k的二叉树最多可以由(2^n-1)个叶子节点，也就是递归过程函数调用的次数，
所以时间复杂度为O(2^n)，而空间复杂度为S(n)。
2.12递归计算n的k次方
递归一般都是逆序思想，要求n的k次方，那就先求n的k-1次方，而要求n的k-1次方，就要求k-2次方，就这样一直给前走，直到求n的0次方为终止条件。而n的k次方就是k个n相乘，所以，只需要每次返回时乘上n就可以得到最终的结果。
int sqrt(int n,int k)
{
if(k==0)
return 1;
else
return n*sqrt(n ,k-1);
}
2.13递归计算一个数字每一位相加的结果
要想得到一个数字的每一位，最简单的办法就是%10 /10，如此反复几次，直到i==0为止，而要让每一位都相加，那就在 return 后面返回一个范围缩小的值 加上%10的值，当函数得到第一位数字时就开始返回结果，这个递归问题是线性的，所以栈桢消耗并不会很大。
public class Test23 {
public static void main(String[] args) {
System.out.println(DigitSum(9878));
}
public static int DigitSum(int i)
{
if(i==0){
return 0 ;
} else {
if((i/10)>0)
{
System.out.println(i%10);
}else{
System.out.println(i%10);
}
return (i%10+DigitSum(i/10));
}
}
}
2.14反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：[“h”,“e”,“l”,“l”,“o”]输出：[“o”,“l”,“l”,“e”,“h”]
示例 2：
输入：[“H”,“a”,“n”,“n”,“a”,“h”]输出：[“h”,“a”,“n”,“n”,“a”,“H”]
class Solution {
public void reverseString(char[] s) {
help(0,s);
System.out.print(s);
}
public void help(int index,char[] s){
if(s==null||index>s.length/2-1){
return;
}
help(index+1,s);
char a=s[index];
s[index]=s[s.length-index-1];
s[s.length-index-1]=a;
}
}
2.15 二叉树的深度
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
public class Solution {
public int TreeDepth(TreeNode root) {
if(root == null){
return 0;
}
int left = TreeDepth(root.left);
int right = TreeDepth(root.right);
return Math.max(left,right)+1;
}
}
2.16平衡二叉树
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
public class Solution {
public int TreeDepth(TreeNode root) {
if(root == null){
return 0;
}
int left = TreeDepth(root.left);
int right = TreeDepth(root.right);
return Math.max(left,right)+1;
}
}
2.17平衡二叉树
汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
这个问题看上去非常困难，实际上理解起来非常简单，为如下三步：
1.把 n-1 号盘子移动到缓冲区
2.把1号从起点移到终点
3.把缓冲区的n-1号盘子也移到终点
所以可以比较容易的写出一个递归的程序：
void hano(char a, char b, char c, int n) {
if (n > 0) {
hano(a, c, b, n-1);
move(a, c);
hano(b, a, c, n-1);
}}
void move(char a, char b){
cout << a << "->" << b << endl;}
这类算法有一个特点，如果你很着急想掌握它，尝试通过背板的方法解决的话，很多时候会失败，因为很容易记错（例如上面的汉诺塔问题），所以对于这类递归问题还是非常建议在第一遍理解了之后再静心自己从零开始考虑一下整个的思路过程。
递归问题中想到思路本身不非常难，真正的难点在于如何优化，但是如果没有任何相关的基础想要出一个思路的话，那还真的是有点令人神情紧张的，尤其是在面试被要求手撕算法的时候。
2.18细胞分裂
细胞分裂 有一个细胞 每一个小时分裂一次，一次分裂一个子细胞，第三个小时后会死亡。那么n个小时候有多少细胞？这个问题的核心就是三个小时为一个周期
// 每三个小时为一个周期 ， 第四个小时就 go die 了。
// 方法一
// 第一个小时，只有a态细胞；第二个小时，a态细胞分裂，原来的a态细胞变成了b态细胞，分裂出来的细胞变成了新的a态细胞；第三个小时，a态细胞继续分裂变成b态细胞和新的a态细胞，b态细胞分裂变成c态细胞和a态细胞；第四个小时，a、b、c态细胞都会分裂，并且按照之前的规律转变。得出下面的结论
// a 初始态 一个小时 前一个小时的 a+b+c
// b 幼年态 两个小时 前一个小时的 a
// c 成熟态 三个小时 前一个小时的 b
function allCell(n){
// a态细胞
let aCell = function(n){
if(n==1){
return 1;
}else{
return aCell(n-1)+bCell(n-1)+cCell(n-1);
}
}
// b态细胞
let bCell = function(n){
if(n==1){
return 0;
}else{
return aCell(n-1);
}
}
// c态细胞
let cCell = function(n){
if(n==1||n==2){
return 0;
}else{
return bCell(n-1);
}
}
return aCell(n)+bCell(n)+cCell(n)
}
console.log(allCell(10))
// 方法二
// 这个方法就是分成了 活着的 和 死亡的
function cell(hour){
// 活着的细胞
function livecell(hour){
if(hour<4){
// 前三个小时没有死亡的细胞 成2的n-1次方增长
return Math.pow(2,hour-1)
}else{
// 从第四个小时开始有死亡的细胞
// 活着的细胞 = 前一个小时活着的细胞 - 这个小时死去的细胞
return livecell(hour-1)*2 - diecell(hour)
}
}
// 死亡的细胞
function diecell(hour){
if(hour<4){
// 前三个小时没有死亡的细胞
return 0
}else{
// 因为三个小时一个周期
// 也就是每三个小时,(n-3)时的细胞就会死完
// 那么 这个小时(n)死去的细胞 + 上个小时(n-1)死去的细胞 + 前两个小时(n-2)死去的细胞 = 前三个小时(n-3)活着的细胞
return livecell(hour-3) - diecell(hour-1) - diecell(hour-2)
}
}
return livecell(hour)
}
console.log(cell(10))
2.19 64格子
有 64 个格子，第一个格子放一粒麦子，第二个放2粒，第三个放4粒…每个格子都是前边的两倍。一共有多少粒？
let sum = 0
let start = 1;
let end = 0;
function tow(){
if(end>=64){
return false
}
sum+=start
start*=2
end++
tow()
}
tow()
console.log(sum)
2.20九九乘法表
// 递归
function num(nums){
if(nums==1){
console.log("1x1=1")
}else{
num(nums-1)
for(var i=1,str='';i<=nums;i++){
str += `${
i}x${
nums}=`+i*nums+' '
}
console.log(str)
}
}
num(9)
// 循环
for(var i=1;i<10;i++){
let str = ''
for(var j=1;j<10;j++){
if(i>=j){
str += `${
j}x${
i}=`+i*j+' '
}
}
console.log(str)
}
3.总结
如果遇到递归较大次数的建议不要使用递归，因为会使我们的内存消耗完。然后在面对算法题目的时候希望大家真的能了解其本质，了解其时间复杂度与空间复杂度。希望大家梦想成真!!!
4.关注我
博客地址
https://blog.csdn.net/weixin_41563161
掘金https://juejin.cn/user/2814360172369271
知乎https://www.zhihu.com/people/hai-kuo-tian-kong-63-38-21
公众号
京公网安备 11010502036488号