递归类题目

2026-09-12

Coding

递归问题的关键点：问题的分解以及每个子问题的求解（其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。）对于每个子问题采用已知上一个子问题的结果的前提下，求解当前子问题的结果。

每次写递归，都应该按照下面三要素：

确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定终止条件：写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
确定单层递归的逻辑：确定每一层递归需要处理的信息。在这里也就会重复调用来实现递归的过程。

链表类题目用递归的方法解决

大部分的链表类题目其实都可以用递归来解决的。详细请见链表类题目的汇总。请见博客Link

二叉树的遍历也是递归

关于二叉树的介绍，请见博客Link

最常用的二叉树的遍历其实就是递归遍历（DFS）和层序遍历（BFS）。

判断两个二叉树是否相同

 /**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        
        //递归遍历树结构
        if(p==nullptr && q==nullptr)//两者都为空
            return true;

        if(
            p!=nullptr && q!=nullptr &&
            p->val == q->val
            )//若是等的，就继续检查
        {
            //先左后右遍历
            auto left_flag=isSameTree(p->left,q->left);
            auto right_flag=isSameTree(p->right,q->right);
            
            return (left_flag && right_flag);
        }
        else
            return false;
    }
};

回溯算法其实也就是递归算法

请见博客^Link关于回溯算法的介绍

其他有意思的递归类题目汇总

外观数列

采用递归的解法：由于递归中带有for循环，时间复杂度为O（N²）,空间复杂度为递归的栈空间

class Solution {
  public:
      string countAndSay(int n) {
  
          if(n==1)
              return "1";
          
          string input_str=countAndSay(n-1);//每次输入的为上一个的结果
          //由于需要基于上一次的结果做处理，为此，需要放在后序的位置上
          int temp_num=1;//初始化为1（多少个1）
          char temp_char=input_str[0];//第一个数
          string result;
          for(int i=1;i<input_str.size();i++)
          {
              if(input_str[i]==temp_char)//还是等于结果的
              {
                  temp_num++;//记录多少个这个数
              }
              else
              {
                  //结果记录为=现有结果+多少个当前字符+当前字符
                  result=result+to_string(temp_num)+temp_char;
                  //然后重置一下
                  temp_char=input_str[i];//新的字符
                  temp_num=1;//当前为1个
              }
          }
          //根据for的终止条件，确定最后一个是否需要补上
          //（把最后漏掉的，补上）
          result=result+to_string(temp_num)+temp_char;
  
          return result;
      }
  };

由于数量只有30个，还有一种解法是打表直接输出全部结果😂,时间复杂度为O(1)，空间复杂度为O(C×M)。其中 C 是 N 是上界，在本题中 C=30，M 为生成的字符串中的最大长度。

但类似这种可以拆分为子问题的解题思路最直接其实还是递归~

统计每个月兔子的总数

#include <iostream>
using namespace std;

int callback(int num_moonth)//求每个月兔子数
{
    //递归的终止条件，月数小于等于2时，只有1只兔子
    if(num_moonth<=2)//月数少于2时为1只
        return 1;
    
    return callback(num_moonth-1)+callback(num_moonth-2);
    //旧兔子每个月生一只；新兔子每两个月就变成一只旧兔子
    //那么只有上两个月的兔子会生出新的兔子，同时加上上一个月的兔子的基数（为旧的兔子数）
}

int main() {
    int N;
    cin>>N;

    int totally=callback(N);
    std::cout<<totally;
}

上面递归算法的思路有点不是太直接，也可以采用下面直接计算

#include <iostream>
using namespace std;

int main() {
    int N;
    cin>>N;

    int num1=1;//1个月的兔子数
    int num2=0;//2个月的兔子数
    int num3=0;//3大于个月的兔子数
    for(int i=1;i<N;i++)
    {
        num3=num3+num2;//两个月长大一个月就是3个月+原本三个月的兔子数
        num2=num1;//原本一个月的，长大了一个月
        num1=num3;//由当前3个月的新生出的

    }
    std::cout<<num1+num2+num3;
}

迷宫问题

#include <iostream>
#include <vector>
using namespace std;

vector<pair<int, int> > result;
void obtains(vector<vector<int>>& matrix, int row, int col, int x, int y, vector<pair<int,int>>& paths)
{
    //将当前点推入paths中
    paths.push_back(make_pair(x,y));
    matrix[x][y]=1;//经过部分设置为1，表示后续不能经过
    if(x==row-1 && y==col-1)//到达终点
    {
        result=paths;
        return;//退出
    }
    //递归的往四个方向搜(没有越界且可以走的)
    if(x-1>=0 && matrix[x-1][y]==0)
       obtains(matrix, row, col,x-1,y,paths);
    if(x+1<row && matrix[x+1][y]==0)
       obtains(matrix, row, col,x+1,y,paths);
    if(y-1>=0 && matrix[x][y-1]==0)
       obtains(matrix, row, col,x,y-1,paths);
    if(y+1<col && matrix[x][y+1]==0)
       obtains(matrix, row, col,x,y+1,paths);
    
    paths.pop_back();//如果都不通过,证明这个点是走不通的删掉最后的这个点
    // matrix[i][j] = 0;//恢复乱标记

}

int main() {
    int row, col;
    cin >> row >> col;//输入数组的行数，列数
    //获取迷宫矩阵
    vector<vector<int>> matrix (row, vector<int>(col,0));
    for(int x=0;x<row;x++)
        for(int y=0;y<col;y++)
            cin>>matrix[x][y];

    //记录走了的路径
    vector<pair<int,int>> paths;
    obtains(matrix, row, col,0,0,paths);

    for(int i=0;i<result.size(); i++)
        cout << "(" << result[i].first << "," << result[i].second << ")" << endl;
}
// 64 位输出请用 printf("%lld")

（跟上面解法本质一样的～）

#include <iostream>
  #include <vector>
  using namespace std;
  
  void obtains(vector<vector<int>>& matrix, int row, int col, int x, int y, vector<pair<int,int>>& paths,vector<pair<int,int>>& result)
  {
      //选择走当前的点。将当前点推入paths中
      paths.push_back(make_pair(x,y));
      matrix[x][y]=1;//经过部分设置为1，表示后续不能经过
  
      if(x==row-1 && y==col-1)//到达终点
      {
          result=paths;
          return;//退出
      }
      
      //递归的往四个方向搜(没有越界且可以走的)
      if(x-1>=0 && matrix[x-1][y]==0)
          obtains(matrix, row, col,x-1,y,paths,result);
      if(x+1<row && matrix[x+1][y]==0)
          obtains(matrix, row, col,x+1,y,paths,result);
      if(y-1>=0 && matrix[x][y-1]==0)
          obtains(matrix, row, col,x,y-1,paths,result);
      if(y+1<col && matrix[x][y+1]==0)
          obtains(matrix, row, col,x,y+1,paths,result);
      
      //类似撤销选择，不走当前的点
      paths.pop_back();//如果都不通过,证明这个点是走不通的删掉最后的这个点
      matrix[x][y] = 0;//恢复乱标记
  
  }
  
  int main() {
      int row, col;
      cin >> row >> col;//输入数组的行数，列数
      //获取迷宫矩阵
      vector<vector<int>> matrix (row, vector<int>(col,0));
      for(int x=0;x<row;x++)
          for(int y=0;y<col;y++)
              cin>>matrix[x][y];
  
      //记录走了的路径
      vector<pair<int, int> > result;
      vector<pair<int,int>> paths;
      obtains(matrix, row, col,0,0,paths,result);
  
      for(int i=0;i<result.size(); i++)
          cout << "(" << result[i].first << "," << result[i].second << ")" << endl;
  }

放苹果

#include <iostream>
using namespace std;

int f(int m, int n) {
    //确定递归的终止条件~
    if (m < 0 || n < 0)//苹果或盘子之一小于0，就无法再往下了（等于的时候，还可以继续，直到有一个为1）
        return 0;
    else if (m == 1 || n == 1)
        return 1;
    else
        return f(m, n - 1) + f(m - n, n);
}

int main() {
    int m, n;
    while (cin >> m >> n) { // 注意 while 处理多个 case
        cout << f(m, n) << endl;
    }
}
/*
放苹果分为两种情况，一种是有盘子为空，一种是每个盘子上都有苹果。
令(m,n)表示将m个苹果放入n个盘子中的摆放方法总数。
1.假设有一个盘子为空，则(m,n)问题转化为将m个苹果放在n-1个盘子上，即求得(m,n-1)即可
2.假设所有盘子都装有苹果，则每个盘子上至少有一个苹果，即最多剩下m-n个苹果，问题转化为将m-n个苹果放到n个盘子上
即求(m-n，n)
*/

24点游戏算法

vector删除中间某个元素：rest.erase(rest.begin() + i)

#include <iostream>
#include <vector>
using namespace std;

bool calculate(vector<int> value_group, double totally_value) {
    //递归终止的条件（当前组用完了~）
    if (value_group.empty()) {
        if (totally_value == 24)
            return true;
        else
            return false;
    }
    //遍历每组数字（任意一个开始都要遍历）
    for (int i = 0; i < value_group.size(); i++) 
    {
        auto rest = value_group;
        // vector删除中间某个元素
        rest.erase(rest.begin() + i);//去掉一个后，剩余的数字组合
        //分别 进行加减乘除4种运算
       if (calculate(rest, totally_value + value_group[i]) //value_group[i]是当前删掉
        || calculate(rest, totally_value - value_group[i])
        || calculate(rest, totally_value * value_group[i])
        || calculate(rest, totally_value / value_group[i]))
            return true;
    }
    return false;//最遍历完都不行的，就返回false
}

int main() {
    vector <int> value_group;
    for (int i = 0; i < 4; i++) {
        int value;
        cin >> value;
        value_group.push_back(value);
    }

    //递归算法
    if (calculate(value_group, 0))
        std::cout << "true" << std::endl;
    else
        std::cout << "false" << std::endl;
}

数组分组

关键是分解问题的思路～

#include <iostream>
#include <vector>
using namespace std;

bool callback(int sum3, int sum5, vector<int> other, int index)
{
    //递归终止的条件
    if(index==other.size())
    {
        return sum3==sum5;//最终检查两个是否相等
    }

    //要么加到3上，要么加到5上
    return callback(sum3+other[index],sum5,other,index+1) || callback(sum3,sum5+other[index],other,index+1) ;

}

int main() {
    int N;
    cin>>N;

    //由于所有5的倍数必须在其中一个组中，所有3的倍数在另一个组中。
    // 因此可以将输入先分为三个组，
    int sum3=0;
    int sum5=0;
    vector<int> other;//其他数先放other中

    int temp;
    while(N--)
    {
        cin>>temp;
        if(temp%5==0)//5的倍数
            sum5+=temp;
        else if(temp%3==0)//3的倍数在另一个组中（不包括5的倍数）
            sum3+=temp;
        else
            other.push_back(temp);
    
    }

    if(callback(sum3,sum5,other,0))
    {
        std::cout<<"true";
    }
    else {
        std::cout<<"false";
    }
}

杨辉三角

大部分的解法都是直接给出二维矩阵，然后逐步推算，但是个人觉得递归的思路更直接～后序遍历

class Solution {
  public:
      vector<vector<int>> generate(int numRows) {
  
          vector<vector<int>> results;
  
          //递归终止条件
          if(numRows==1)
          {
              results.push_back(vector{1});
              return results;
          }
          // if(numRows==2)
          // {
          //     results.push_back(vector{1,1});
          //     return results;
          // }
  
          //除了1和2以外
          vector<int> cur_row;
          auto previous_result=generate(numRows-1);//之前的所有结果
          results=previous_result;//之前的全部结果
          auto last_row=previous_result.back();//上一行
  
          // 后序的位置，进而从下往上
          for(int i=0;i<numRows;i++)
          {
              if(i==0)//第一个数
                  cur_row.push_back(1);
              else if(i==numRows-1)//最后一个数
                  cur_row.push_back(1);
              else
              {
                  int cur_value=last_row[i]+last_row[i-1];//上一行的两个值相减
                  cur_row.push_back(cur_value);
              }
          }
          results.push_back(cur_row);//每一行的结果放入
          return results;
      }
  };

参考资料

My Leetcode