跟踪递归调用

Question

我正在学习递归的概念，为了练习我的知识，我编写了以下程序。

#include <bits/stdc++.h>

using namespace std;

int c = 0;

int add(int a) {
  if (a == 0) {
    return c;
  }
  c = c + 1;
  add(a - 1);
  cout << "Hello";
}

int main() {
  int x = add(6);
  cout << "Final " << x;
}

它产生了这个输出，这不是我所期望的：

HelloHelloHelloHelloHelloHelloFinal 5134464

为什么当 a==0 条件满足时程序没有终止并且它 returns 主函数的最终结果？

相反，它打印了 "Hello" 6 次，但输出语句在递归调用之后。

为什么递归调用后的代码还是执行了多次？

我预计它永远不会被执行。

我仍在努力理解递归的工作原理，所以我想知道这里到底发生了什么。

Answer 1

经验法则：递归函数中的Return语句最好是函数的最后一条语句

你看，你正在返回 c，但你没有将它存储在任何地方！

我相信这就是您要查找的代码：

#include <iostream>

void practiceRecursion(const int& a, int& c) {
    if (a != 0) {
        c++;
        practiceRecursion(a-1, c);
    }
}

int main() {
    int a = 6;
    int c = 0;
    practiceRecursion(a, c);
    // whatever you wish to do with c
    return 0;
}

Answer 2

已发布函数的主要问题是它具有 undefined behavior。

int add(int a) {     // Note that this function is supposed to return an int.
  if (a == 0) {
    return c;        // <- Ok, recursion stopped, first exit point.
  }
  // else 
  c = c + 1;
  add(a - 1);        // Recursive call. When it returns, the execution continue
                     // from here, it does not jump diretly back to main.
                     // That's exactly what would happen if instead of `add`
                     // here, there were a call to another function, say `foo(a-1);`
                     // You would expect the excution to continue after it, don't you?
  cout << "Hello"; 

  // Here a return statement is missing (second exit point) => UB
  // The strange number you see in the output is a result of that. Maybe 
  // return c; 
}

程序执行时你看到的是这样的

call to add() with argument 6
    call to add() with argument 5
        call to add() with argument 4
            call to add() with argument 3
                call to add() with argument 2
                    call to add() with argument 1
                        call to add() with argument 0
                            return 0
                        print "Hello"
                        return garbage (ignored)
                    print "Hello"
                    return garbage (ignored)
                print "Hello"
                return garbage (ignored)
            print "Hello"
            return garbage (ignored)
        print "Hello"
        return garbage (ignored)
    print "Hello"
    return garbage, which is stored in x
print "Final" and whatever is in x

跟踪递归调用

Tracing recursion calls

c++

recursion

output