梦想成真---递归详解
记得在2023年春招美团第三轮主管面试中遇到一道关于递归的问题。后来总结发现,第三轮总管面试倾向于设置一些非传统性问题来考察应聘者的综合能力。当时确实感到紧张不安,并意识到对递归算法的理解还有待加强。因此未能如愿通过面试并遗憾地与美团错过了合作机会。作为程序员群体而言，默认掌握的最基础也是最重要的算法之一就是递归。因此建议大家在准备此类考试或面试时要认真对待每一个细节和知识点。以下是我整理了一些常见的递归题类型,通过深入理解这些问题类型并加以练习应对各种变体问题。
1.序
递归作为计算机科学的核心概念具有重要意义。它构成了多种算法与数据结构的基础基石。因此，在众多新手面前学习递归常常会遇到相当大的挑战。
实现自调用函数的关键在于，在每次自调用执行时会将给定的问题分解为更小的子问题。自调用过程会持续下去，直到这些子问题能够直接解决而不需进一步分解为止。
为了确保递归函数不会导致无限循环，它应具有以下属性：
一个简单的基础示例（basic example）（或其他相关案例）——一种无需递归实现的答案终止方案。
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=251 17 17 3 2 华为笔试题)
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个数值的话，则会面临巨大的挑战——这会导致使用的栈空间变得非常大。为了更直观地理解这一过程，在这里我可以向你展示一张图示。
此外，在分析算法效率时发现：当递调用次数不断增加时（其时间复杂度也随之升高），综合以上两点考虑（我认为使用非递调结构替换为循环结构是明智之举）。然而，并非全盘否定其价值（虽然在这种情况下表现欠佳），实际上在某些场景下它仍然展现出其强大的优势。
斐波那契数列的计算过程其核心思想在于每一项都是前两项之和因此将其嵌入递归算法中则可分解为若干子问题逐步推进至基准情况当基准情况出现时则停止执行并开始回溯计算最终结果
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的情况时，在递归调用的过程中（算法运行中），该算法在处理参数为3的情况时会进行2次计算；而当参数为2时，则需要执行3次运算；对于参数为1的情况，则会触发5次调用；最后在参数为0的情况下，则需要进行3次计算。
当递归函数的出口条件为n \geq 2时，在执行过程中该函数会不断在其调用栈上开辟新的空间区域；从而容易导致栈溢出现象的发生
深度为n−1的二叉树能够容纳最多2^{n−1}个叶子节点；对于高度k的最大完全二叉树来说,其最大叶子数量是2^k−1；完全二叉树结构下的递归函数调用次数即为其叶子节点数量
所以时间复杂度为O(2^n)，而空间复杂度为S(n)。
2.12递归计算n的k次方
递归通常采用逆序思维策略，在实现过程中我们一般会将pow函数定义为一个迭代过程。具体来说，在实现过程中我们一般会将pow函数定义为一个迭代过程。
其中，在实现过程中我们通常会将pow函数定义为一个迭代过程。
具体来说，在每层函数返回时都需要将当前结果与另一个参数相乘即可。
int sqrt(int n,int k)
{
if(k==0)
return 1;
else
return n*sqrt(n ,k-1);
}2.13递归计算一个数字每一位相加的结果
想要获取一个数字的每一位最直接的方式就是不断地进行模运算和除法操作持续多次直到变量i等于零。然后将这些位上的数值累加起来一旦函数处理完最高位数字后就开始计算总和这个问题是线性的因此栈帧消耗不会很高。
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细胞分裂
在每个小时里进行一次连续性生长（cell division），每次生长都会产生一个新的子细胞（subcell）。到第三个小时时这些子细胞将全部死亡（die）。那么经过n个小时之后会有多少个子细胞存活？这个问题的核心在于每隔三个小时就会形成一个新的生长周期（cycle）。
// 每三个小时为一个周期 ， 第四个小时就 go die 了。
// 方法一
// 在第一个小时里仅存在A型细胞；到了第二个小时原有的A型细胞发生了分化生成了B型的母体单元而新生成的则是A型的小个体；第三个小时不仅原有的A型母体单元继续分化出更多的B型单元还形成了新的A型个体与此同时原有的B型单元也开始分化产生C型单元并保留着原有的A型结构；第四个小时所有三种类型的单元都会进行一次完整的增殖并按照前面所描述的方式依次进行状态转换
// 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个小方块，在第一块放置一粒小麦，在第二块放置两粒小麦，在第三个小方块中放入四颗小麦……每一个后续的小方块都放置前一个的两倍数量。请问总共需要多少颗小麦？
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://juejin.cn/user/2814360172369271
知乎https://www.zhihu.com/people/hai-kuo-tian-kong-63-38-21
公众号
