无法理解为什么这 19 行 C++ 代码正在执行所需的任务（使用递归）所以我制作了它的堆栈但仍然存在问题

Question

所以，我的问题是编写一个 C++ 程序来使用递归打印给定字符串的所有子字符串。那是在一个免费的 youtube 课程中，老师只是在没有详细解释的情况下讲述问题和答案。所以，我复制了该代码并执行了它，它正在运行，但我想检查堆栈是如何管理的，所以我创建了堆栈并发现了一个问题。

您可以在这张图片中查看问题的详细信息，例如问题陈述、c++ 代码、输出、解释、堆栈等：https://photos.app.goo.gl/yQuiSFwfVB4GnDGg9

我也在这里附上代码：

#include<iostream>
using namespace std;
void sub( string s, string ans="")
{
    if(s.length()==0)
    {
        cout<<ans<<endl;
        return;
    }
    char ch = s[0];
    string ros = s.substr(1); //ros- Rest of the string
    sub(ros,ans);
    sub(ros,ans+ch);
}
int main()
{
    sub("ABC","");
    return 0;
}

而代码的输出是：

C

B

BC

A

AC

AB

ABC

编辑：很难用语言表达这个问题，但我会尝试。堆栈不断调用该函数，直到它达到基本条件和 returns。因此，根据代码，每个函数调用都会调用该函数两次，并且这种情况会一直发生，直到达到基本条件。因此，它看起来类似于二叉树（如图所示）。现在，问题是编译器没有执行该树的最后 2 个节点。

让我尝试详细说明一下。我将尝试讲述该函数如何执行和创建堆栈，但我将主要关注第二次调用 sub(ros,ans+ch) 并忽略第一次调用 sub(ros,ans) 因为问题是sub(ros,ans+ch) 的倒数第二个调用没有被执行。

因此，主函数将调用 sub("ABC","")，这将调用 2 个函数 sub("BC","") 和 sub("BC","A")。让我们忽略 sub("BC","").

sub("BC","A") 将调用 2 个函数，即 sub("C","A") 和 sub("BC","AB")。让我们再次忽略第一个电话。

sub("BC","AB") 将调用 sub("C","AB") 和 sub("C","ABB")。再次忽略第一个调用意味着：

sub("C","ABB") 将调用 sub("","ABB") 和 sub("","ABBC")。

这 2 个调用将达到基本情况，应该在程序结束时打印 ABB 和 ABBC，但它没有发生。

根据堆栈，输出是正确的，但它应该有另外 2 行包含字符串 ABB 和 ABBC 的输出，但这并没有发生。自过去 24 小时以来，我已经多次检查堆栈执行情况，但我没有发现任何问题。感谢任何帮助，谢谢。

Answer 1

您可以检测函数以更清楚地看到发生了什么：

#include<iostream>
using namespace std;
void sub( string s, string ans="",int stack_counter =0)
{
    std::cout << "\n";
    std::cout << stack_counter << " inp " << s << " " << ans << "\n";

    if(s.length()==0)
    {
        cout<<ans<<endl;
        return;
    }
    char ch = s[0];
    string ros = s.substr(1); //ros- Rest of the string
    std::cout << stack_counter << " call sub(" << ros << "," << ans << ")";
    std::cout << " and sub(" << ros << "," << (ans+ch) << ")\n";
    sub(ros,ans,stack_counter+1);
    sub(ros,ans+ch,stack_counter+1);
}
int main()
{
    sub("ABC","");
    return 0;
}

输出为：

0 inp ABC 
0 call sub(BC,) and sub(BC,A)

1 inp BC 
1 call sub(C,) and sub(C,B)

2 inp C 
2 call sub(,) and sub(,C)

3 inp  


3 inp  C
C

2 inp C B
2 call sub(,B) and sub(,BC)

3 inp  B
B

3 inp  BC
BC

1 inp BC A
1 call sub(C,A) and sub(C,AB)

2 inp C A
2 call sub(,A) and sub(,AC)

3 inp  A
A

3 inp  AC
AC

2 inp C AB
2 call sub(,AB) and sub(,ABC)

3 inp  AB
AB

3 inp  ABC
ABC

sub("ABC","") which will call 2 functions sub("BC","") and sub("BC","A"). Lets ignore the sub("BC","").

正确。

0 inp ABC 
0 call sub(BC,) and sub(BC,A)

The sub("BC","A") will call 2 functions that are sub("C","A") and sub("BC","AB").

错了。

1 inp BC A
1 call sub(C,A) and sub(C,AB)

sub("BC","A") 调用 sub("C","A") 和 sub("C","AB").

无法理解为什么这 19 行 C++ 代码正在执行所需的任务（使用递归）所以我制作了它的堆栈但仍然存在问题

Unable to understand why this 19 lines C++ code is doing the required task (using recursion) so I made its stack but there is still an issue

c++

visual-c++

c++11

c++14

c++17