时间戳

首页 > 解决方案 > 这个递归函数在 C++ 中是如何工作的？

c++ - 这个递归函数在 C++ 中是如何工作的？

问题描述

我目前正在上一门 C++ 课程，我们正在学习递归，在课堂上我的教授使用这个函数作为递归的例子，该函数旨在返回一个数字中的最小数字，并且是：

int smallD(int n) {
    if (n < 10) return n;
    int x = smallD(n / 10);
    if (x < n % 10) return x;
    else return n % 10;
}

我对将 x 设置为递归调用的工作原理感到困惑，在 n < 10 之前，该函数是否会继续运行 n / 10，我真的不理解这个概念，并且可以使用一些关于该函数如何工作的指针。

标签： c++recursion

解决方案

这里有一些有助于理解递归的东西。添加打印语句以观察代码，因为它递归地调用自身并传递和“缩进级别”以提供帮助。

获取原始的缩小代码并将其扩展为更具可读性的内容，并为其添加额外的调试信息。

int smallD(int n, const std::string& indent) {

    cout << indent << "enter: smallD(n=" << n << ")" << endl;

    if (n < 10)  {
        cout << indent << "n < 10 => returning: " << n << endl;
        return n;
    }

    cout << indent << "about to recurse inovking smallD(" << n / 10 << ")" << endl;
    int x = smallD(n / 10, indent+"  "); // grow the indent by 2 spaces
    cout << indent << "return from recursion, result is: " << x << endl;

    cout << indent << "x=" << x << "  n=" << n << " n%10=" << n % 10 << endl;

    if (x < n % 10) {
        cout << indent << "x is less than n%10, returning: " << x << endl;
        return x;
    }

    cout << indent << "x is greater than or equal n%10, returning: " << n%10 << endl;
    return n % 10;
}

让我们通过调用来尝试一下smallD(8942468, "")

enter: smallD(n=8942468)
about to recurse inovking smallD(894246)
  enter: smallD(n=894246)
  about to recurse inovking smallD(89424)
    enter: smallD(n=89424)
    about to recurse inovking smallD(8942)
      enter: smallD(n=8942)
      about to recurse inovking smallD(894)
        enter: smallD(n=894)
        about to recurse inovking smallD(89)
          enter: smallD(n=89)
          about to recurse inovking smallD(8)
            enter: smallD(n=8)
            n < 10 => returning: 8
          return from recursion, result is: 8
          x=8  n=89 n%10=9
          x is less than n%10, returning: 8
        return from recursion, result is: 8
        x=8  n=894 n%10=4
        x is greater than or equal n%10, returning: 4
      return from recursion, result is: 4
      x=4  n=8942 n%10=2
      x is greater than or equal n%10, returning: 2
    return from recursion, result is: 2
    x=2  n=89424 n%10=4
    x is less than n%10, returning: 2
  return from recursion, result is: 2
  x=2  n=894246 n%10=6
  x is less than n%10, returning: 2
return from recursion, result is: 2
x=2  n=8942468 n%10=8
x is less than n%10, returning: 2    // <== this is the final result

因此，希望这将帮助您了解递归的工作原理。

推荐阅读