C++ 如果此文颠覆你的认知，可能你对递归只是一知半解

一枚大果壳

发布于 2024-04-30 13:12:39

1140

发布于 2024-04-30 13:12:39

文章被收录于专栏：编程驿站

1. 前言

无递归，不算法。无论怎样强调递归的重要性，都不为过。受限于计算机的思维能力，计算机的计算找答案的过程就是在不停试错、纠正错误的过程，类似于爱迪生发明灯炮。递归能帮助我们在不知道计算边界的情形下试错。

多函数求解过程，相当于多人协助完成一件事情，必然会有半成品的相互传递和再加工过程。了解递归的内部细节，对于正确使用递归将有巨大帮助。

2. 递归的两条线

递归调用过程分递进和回溯两个过程，传值和计算可以分别在这两个过程中实现。

2.1 递进线

先拿出一个简单的案例。如求解一维数组 int n[5]={5,1,8,9,3}中所有数据相加的。

很认同一个大咖说过的一句话，任何问题都可以当成树来看待。当然，自会有人反对，这么简单的问题，还当成树结构来理解，是不是有点孔乙己了。如果解题的境界仅停留在结果层面上，则追求有点低了。应该是发现、归类。如果能明白所有题目都是一类，便是大境界了。

废话一下后，给一维数组画一个树结构图。不要质疑，只是这棵树只有一条分支。树的定义是空节点都是树，何况还有一条枝桠。

这道题目，自然是要用递归。递归有两条线，递进线、回溯线。这两条线中都可以进行值传递和计算。不言而喻，递进线上的值要从根节点一直传递到叶节点，最终结果要到最后叶节点位置收割。

如何收割最终结果？

使用全局变量在递进的终点收割结果。

算法实现：

#include <iostream>
using namespace std;
int n[]= {5,1,8,9,3};
//全局变量
int sum=0;
/*
* idx 递进深度
* s   父节点传递给子节点的值
*/
void getSum(int idx,int s) {
 //递进终点
 if( idx==4 ) {
  //父节点传递过来的值和自身值求和，存储在全局变量中
  sum= s+n[idx];
  return;
 }
 //不是叶节点,用当前节点的值加上父节点传递过来的值
 s+=n[idx];
 getSum(idx+1,s);
}
int main(int argc, char** argv) {
 getSum(0,0);
 cout<<sum;
 return 0;
}

回溯时返回。递进终点得到最终答案后，向上回溯到父节点。所有父节点只是一个过道，对返回的值不做任何处理，一直返回到最早调用处。

算法实现：

int getSum_(int idx,int s) {
 //递进终点
 if( idx==4 ) { 
  return  s+n[idx];;
 }
 //有向下传也有向上升状态 
 int sum= getSum_(idx+1,s+n[idx]);
 //父节点只是过道,得到后直接向上推 
 return sum;
}
int main(int argc, char** argv) {
 int res=getSum_(0,0);
 cout<<res; 
 return 0;
}

这种方式，通过递进线把父节点累加后的值向下传递。到达递进终点，累加出最终结果后，又一路绿灯通过父节点传递到调用根节点的位置。

这条U形链还可以在递归算法中求区间和。

如求解[1,4]，即一维数组某个位置到最后位置的的数字之和。本文由简单案例理解递归中的细枝末节，不要较真为什么要用递归做这么简单的问题。

int getSum_(int idx,int s,int left) {
 //递进终点
 if( idx==4 ) { 
    //得到答案，向上返回
        return  s+n[idx];;
 }
 int sum= getSum_(idx+1,s+n[idx],left);
    //回溯过程中，如果发现回到了左边界位置。计算区间和
 if(idx==left)sum-=s; 
 return sum;
}
int main(int argc, char** argv) {
     //求解 [1,4]区间之和 
 int res=getSum_(0,0,1);
 cout<<res; 
 return 0;
}

能不能只在递进过程，得到任何区间值的和？

这里的说的只在递进过程，指结果一定要在递进过程求解到。回溯只把值向上传递。

肯定是可以，先借助全局变量实现。为什么要用全局变量，因为刚才说了，只在递进过程中完成，需要用全局变量记录左边界的前缀和。

int ls=0,s1=0;
void getSum_(int idx,int s,int left,int right) {
 //进入左边界  用全局变量记录左边界的前缀和
 if(idx==left)ls=s;
 //进入右边界 计算左、右区间的和
 if(idx==right) {
  s1= s+n[idx]-ls;
  return;
 }
 return getSum_(idx+1,s+n[idx],left,right);
    //计算过程没有出现在回溯过中
}

int main(int argc, char** argv) {
 getSum_(0,0,1,3);
 cout<<s1;
 return 0;
}

不借助全局变量也可以，无非多加一个参数，把左边界的前缀和向下一直传递到右边界函数。

void getSum_(int idx,int s,int left,int right,int ls) {
 //进入左边界 
 if(idx==left)ls=s;
 //进入右边界 
 if(idx==right) {
  s1= s+n[idx]-ls;
  return;
 }
 return getSum_(idx+1,s+n[idx],left,right);
}
int main(int argc, char** argv) {
 getSum_(0,0,1,3,0);
 cout<<s1;
 return 0;
}

看来，我们只要把递归过程中的始末了解的清清楚楚。如何玩代码，就一切在掌控之中。

在求区间和时，如果允许在回溯过程中计算，则简单多了。在递进到右边界时向上传递累加值，在回溯到左边界时计算结果。

int getSum(int idx,int s,int left,int right) {
 //递进到右边界,累加到此的和后向上传递
 if(idx==right) {
  return s+n[idx];
 }
 int sum= getSum(idx+1,s+n[idx],left,right);
    //如果回溯到了左边界，则可求解左右区间和
 if(idx==left)return sum-s;
    //不是左边界，继续向上传递
 return sum;
}
int main(int argc, char** argv) {
 int res= getSum(0,0,1,3);
 cout<<res;
 return 0;
}

至此，我们主要重用递进线，在此线上做计算。回溯线只作传输带。

2.2 回溯线

现在开始要玩回溯线了。递进线不做任何计算，所有计算留在回溯线上，看是否一样玩转前面的求解。

还是从求解整个数组的数字之和开始。这个很容易实现，递进线跑空档，一路到递进终点，然后回溯过程逐层累加。

int getSum1(int idx) {
 //如果终点 
 if(idx==4) {
  return n[idx];
 }
 //得到返回值
 int sum= getSum1(idx+1);
 return sum+n[idx];
}

int main(int argc, char** argv) {
 int res= getSum1(0);
 cout<<res;
 return 0;
}

这个代码看起来好标准，是的，就是平时常用的一种分治思想。先计算子问题，回溯时合并子问题和自身的答案。

好，能否只在回溯中求解区间和。当然可能，只要你有所求，我就有解。而且还很简单。

在递进到右边界时，停止递进，带着右边界的值向上回溯。
回溯到上一层时，累加回溯值和当前值的和，然后继续回溯。
回溯到左边界时，累加。然后回溯。
如果层次小于左边界，不能做累加，仅回溯。

如下图，示区间[1,4]之间的数字之和。

算法实现

int getSum2(int idx,int left ,int right) {
 //如果到达右边界
 if(idx==right) {
  return n[idx];
 }
 //得到返回值
 int sum= getSum2(idx+1,left,right);
    //如果层次小于左边界，仅带值向上传递
 if(idx<left)return sum;
    //其它时候都要累加
 else return sum+n[idx];
}
int main(int argc, char** argv) {
 int res= getSum2(0,1,3);
 cout<<res;
 return 0;
}

如果现在要你只能在回溯过程中求区间最大值，你是否也能很快求出来。

到此，你是不是对递归算法另眼相看，当你了解其中曲径。当是可以来去自由。

不过，下面来一个多叉树。

3. 多叉树

现在有一棵多叉树，怎样只在递进线或回溯线上求任意子树的深度。如下图中，求节点4的最深子树的长度。

先抛开树中其它的节点，对它们视而不见。画出以节点4为根的树的递进线和回溯线。有三条递进线，三条回溯线。既然要求树的最大深度，则需要求出每一个子树的深度后，再找出最大值。

现在变成怎么求任一子树的深度，原理无非就是数数。可以在递进时数数，也可以在回溯时数数。

3.1 递进时数数

从根节点开始报数，每递进一层，报数加一。递进线终止时，即可以使用全局变量记录此子树的深度，也可以通过回溯线向上汇报最终结果。

如下使用回溯线向根节点汇报情况。

算法实现：

树的回溯线的终点有两处。

一处是当它的某一个子树处理完毕。如果有多个子树，则有多条子树回溯线。
一个是当所有子树处理完毕，自己向上回溯。

因为是向下传递，进入任何一个节点时，可知从根节点到此节点的深度。

如上面的树节点4有3棵子树，每一棵子树回溯到节点4时，统计其中最大深度，意味要统计三次。

当所以子树处理完毕后，把最终结果向调用者上交。

#include <bits/stdc++.h>
using namespace std;
//构建节点关系
int trees[14][14];
int n;
void init() {
 for(int i=1; i<=n; i++)
  for(int j=1; j<=n; j++)trees[i][j]=0;

 int f,t;
 for(int i=1; i<n; i++) {
  cin>>f>>t;
  trees[f][t]=1;
 }
}
/*
* 通过递进线向下传递深度值。
*/
int findTreeDep(int root,int dep) {
    //进入此节点，可得到由向向下传递过来的深度
 int maxRes=dep;
 for(int i=1; i<=n; i++) {
  if( trees[root][i]!=0 ) {
             //计算子树的深度
   int res=findTreeDep(i,dep+1);
             //某一个子树回溯完毕，当然要检查哪一棵子树的深度最大
   maxRes= max(maxRes,res);
  }
 }
    //所有子树回溯完毕，当然是把最终结果上交
 return maxRes;
}
int main() {
 cin>>n;
 init();
 int res= findTreeDep(4,0);
 cout<<res;
 return 0;
}

相当于把一个初始值向下传递的过程逐步增大，计数完毕后，又逐步向上汇报。

3.2 回溯时数数

因为递进时没有任何信息传递下来。对于任何一个节点，初始只知道自己的高度，也就是0。当有子树回溯时，子树会把自己的高度传过来，当前节点可以根据子树返回的高度更新自己的高度。

当所有子树回溯完毕后，也就知道了离自己最深的子树有多远。

#include <bits/stdc++.h>
using namespace std;
//构建节点关系
int trees[14][14];
int n;
void init() {
 for(int i=1; i<=n; i++)
  for(int j=1; j<=n; j++)trees[i][j]=0;

 int f,t;
 for(int i=1; i<n; i++) {
  cin>>f>>t;
  trees[f][t]=1;
 }
}

//查找子树
int findTreeDep_(int root) {
    //因为没有任何递进信息，初始只能有对自己的认知，自己的高度为 0。
 int maxRes=0;
 for(int i=1; i<=n; i++) {
  if( trees[root][i]!=0 ) {
             //因为是回溯传递计算值，子树会把自己的高度向上传递
   int res=findTreeDep_(i);
             //根据子树高度更新自己的高度
   maxRes= max(maxRes,res+1);
  }
 }
    //知道自己现在的的最高深度后再向上传递
 return maxRes;
}
int main() {
 cin>>n;
 init();
 int res= findTreeDep_(4);
 cout<<res;
 return 0;
}

在树中使用递归中，如果能弄明白函数中的三个位置，凡是涉及到树或图的问题都能较容易求解。