• 引言&致谢

  首先，特别感谢我亲爱的舍友张栋辰同学，他提出的汉诺塔问题让我发现我对递归的理解实则一窍不通且极其错误，让我感受到了是部分知识的缺失导致了对递归的难以透彻理解。如果对递归理解有失偏颇可以先从后面看再看前面的题解部分。 同时，也对参与讨论最后的越界问题的贾天宇同学表示诚挚的感谢，虽然当时我们除了它越界外什么都没讨论出来（ '▿ ' ） 最后感谢文心一言4.0，它和我聊了将近一个小时抽丝剥茧指出了关于数组越界导致的全局变量错误读写的问题，以及提供了许多细节性问题的解答。

• 题面

  

• 递归实现的深度优先搜索

  首先，我们使用DFS来生成一棵树，先给出板子：

  #include <iostream>
  #define N 8
  using namespace std;
  
  int a[4];
  long long cnt;
  //i:深度，j:当前数字
  bool cut(int i,int j){//剪枝
    if(i>0 && a[i-1]/2<j){
        return false;
    }
    return true;
  }
  void dfs(int i){
    int k;
    if(i == N){//最大深度回溯
        cnt++;
    }else{
        for(int j = 0;j<=N;j++){
            if(cut(i,j)){
                a[i] = j;
                dfs(i+1);//增加深度
            }
        }
    }
  }
  int main(int argc, char const *argv[])
  {
    a[0] = N;
    dfs(1);
    cout << cnt << endl;
    return 0;
  }

  通过dfs，列举出符合条件的笛卡尔集，最终给出cnt的值。[[递归]]

• 动态规划

• 推导

  

  （最后一列少了个 248） 不难发现，对$n=8$的情况而言，实际上在8后面加上去的数字就是$1,2,3,4$，这几个数所对应的满足条件的笛卡尔集元素个数已经计算过，同样，对于$1,2,3,4$来说，同样满足满足条件的个数是截取一半的数后的和再加上本身，那么得到状态转移方程：

  $$\begin{array}{rl}f(n)& =\sum _{i=1}^{\frac{n}{2}}f(i)+1,nmod2=0\\ f(n)& =f(n-1),nmod2\ne 0\end{array}$$

  根据初步得到的状态转移方程，我们只需多次递归调用该方程，将所有问题转化为最小规模的子问题，即:

  $$f(1)=1$$

  因此现在我们其实不需要再用深搜枚举。

• 动态规划初步优化

  #include <iostream>
  using namespace std;
  
  long long f(int n){
    long long cnt = 0;
    if(n == 1) return 1;
    for(int i = 1;i<=n/2;i++){
        cnt += f(i);
    }
    return cnt + 1;
  }
  
  int main(int argc, char const *argv[])
  {
    int n;
    cin >> n;
    cout << f(n) << endl;
    return 0;
  }

• 优化成递推

  因为n为奇数的情况也可以转化为n为偶数的情况，这里只讨论n为偶数的情况

  $$\begin{array}{rl}f(n)& =f(1)+f(2)+...+f(\frac{n-1}{2})+f(\frac{n}{2})\\ f(n-1)& =f(1)+f(2)+...+f(\frac{n-1}{2})\end{array}$$$$\therefore f(n)=f(n-1)+f(\frac{n}{2})$$

  多写几项，发现这其实已经是一个递推关系了，也就是说，一个递归问题已经被优化成了一个递推问题，代码实现也相当简单了：

  #include <iostream>
  using namespace std;
  long long a[2005];
  int main(int argc, char const *argv[])
  {
    a[1] = 1;
    int i = 1;
    while(i<=2001){
        i++;
        if(i % 2 == 0) a[i] = a[i-1] + a[i/2];
        else a[i] = a[i-1];
    }
    cout << a[2001];
    return 0;
  }

  其实说白了就是高中的数列问题，只不过高中求出这个通项不可能手算，而计算机能够解决，当然，前提是你要给出最小规模的特定解（或者说是容易求出的解）。

• 关于递归的深入思考

  我们看一些文章，往往告诉我们不必关注递归函数的执行细节（但这么说并不意味着不应当掌握递归函数的调用过程），但往往正是因为对执行细节的认知缺失让我们无法理解递归函数的工作方式，进而无法用递归思想解决问题，然而，递归函数求解问题的使用频率非常高，从上述例子也不难看出来，递归的初步实现往往是后续优化算法并且检验程序正确性的重要依据，所以，我们不妨通过最基本的汉诺塔问题重新思考一下究竟什么是递归。

• 汉诺塔问题

  首先回顾下汉诺塔的规则：将A柱的所有盘子挪到C柱。 核心思路大家也都知道了，要将$n$个盘子挪到C柱，先将$n-1$个盘子通过C柱挪到B柱，然后再将剩下的一个盘子由A柱挪到C柱，最后再将$n-1$个盘子从B挪到C。

  这里递归的思想可以将问题规模不断变小，一个五层的汉诺塔可以拆分成两个四层的汉诺塔问题，依次类推，我们不难发现这个规模逐步减小的问题存在一个边界条件，即$n=2$的时候，这是最小的满足上述核心思路的情况。

  也就是说，更小的规模$n=1$已经不满足普适的递归条件，因为现在已经没有$n-1$个盘子要先放到辅助杆上，我们只要把唯一剩下的这个盘子挪到目标柱上去就行了。因此递归函数特判了$n=1$的下一层递归传入的参数$n=0$，直接return终止该分支的递归调用，使得递归深度达到最深，然后向上一层函数回溯。

  由此写出递归的递归函数：

  void move(char start, char destination)
  {
    cout << start << "--->" << destination<<endl;
  }
  
  void hanoi(int n, char start, char medium, char destination){
    if (n == 0) return;
    else{
        hanoi(n - 1, start, destination, medium);
        move(start, destination);
        hanoi(n - 1, medium, start, destination);
    }
  }

  接下来我们详细探究下这个递归函数的调用过程，找遍全网只有这一张看上去很吃力的图 这里我把它转绘了一下，体现一下递归调用时的函数调用栈，$f,p$分别为递归函数hanoi和移动函数move 其实在每一次递归调用过程中，都会在内存中开辟一块新的空间，即栈帧（Stack Frame），也叫函数调用栈，存放存放着函数参数，局部变量及恢复前一栈帧所需要的数据，在这张图上体现为每个函数下方的方框。跟着箭头即可走完整个递归的调用流程。这张图并没有体现函数栈帧全部内容，我只是象征性的标了几个*next，即指向下一栈帧的指针，大致理解调用过程即可。

  下图是一个栈帧，详细请看

• 递归中的局部变量与函数栈帧

  long long f(int n){
    long long cnt = 0;
    if(n == 1) return 1;
    for(int i = 1;i<=n/2;i++){
        cnt += f(i);
    }
    return cnt + 1;
  }

  回顾上面第一次动态规划的递归程序，我们可能会好奇这个long long cnt = 0;为什么可以这么写？为什么每次调用都能创建一个cnt？我们最后返回的是哪个cnt呢？

  这次画的就比较随意，只需要知道每次创建函数栈帧是都会在其中创建一个局部变量cnt，cnt最后逐级相加汇总到最初的栈帧，最后return回调用的地方就是了。

• 递归越界时对全局变量的影响

  #include <iostream>
  #define N 4
  using namespace std;
  
  int a[2];
  long long cnt;
  //i:深度，j:当前数字
  bool cut(int i,int j){
    if(i>0 && a[i-1]/2<j){
        return false;
    }
    return true;
  }
  void dfs(int i){
    int k;
    if(i == N){
        cnt++;
    }else{
        for(int j = 0;j<=N;j++){
            if(cut(i,j)){
                a[i] = j;
                dfs(i+1);
            }
        }
    }
  }
  int main(int argc, char const *argv[])
  {
    a[0] = N;
    dfs(1);
    cout << cnt << endl;
    return 0;
  }

  这其实和递归以及递归创建的函数栈帧没有关系（全局变量不在栈帧中存储副本），只是借着递归背景讲一下这个正好踩的坑。

  用较小规模的$f(4)$举例，这时候最长的数字可以是124，是三位，那么我这里开a[2]肯定开小了，但我们输出cnt变量每次自增操作时前后的值会发现,全局变量cnt的变化是：

  0 1
  0 1
  0 1
  1 2
  4294967298 4294967299
  4294967299

  也就是说，cnt的值遭到了意外的修改，对于这样一个简短的静态内存程序来说，越界访问a\[i-1]/2居然没有抛异常，说明a\[i-1]虽然越界，但这个位置存储的确实是一个数字类型的变量，再加上cnt变量被异常修改，以及除了cnt++以外唯一的越界赋值语句i\[i]＝j，可以判定，这个越界的位置存储的正是cnt的值，因此数组的越界访问导致了全局变量cnt的错误修改，导致程序异常。

  当然，这不是递归的问题，因为深度i又不会越界，递归依旧搜索到深度N再回溯，这没有任何问题，只是计数变量cnt表现的很奇怪而已，不要因为这个怀疑自己对递归有什么误解。

  本人才疏学浅，若内容有误欢迎各位大师斧正，鄙人先行谢过各位看官。

• /