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

user_14976810 0
Viewed 103

So, my question is to write a C++ program to print all the substrings of a given string using recursion. It was in a free youtube course in which the teacher just tells questions and their answer without a detailed explanation. So, I copied that code and executed it and it was working but I wanted to check how the stack is being managed so I made the stack and found an issue.

You can check the details of the question like the question statement, c++ code, output, explanation, stack, etc. in this image: https://photos.app.goo.gl/yQuiSFwfVB4GnDGg9

I am also attaching the code here:

#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;
}

And the output of the code is:

C

B

BC

A

AC

AB

ABC

EDIT: It is hard to tell the issue in words but I will try. The stack keeps calling the function till it reaches the base condition and returns. So, according to the code, every function call will call the function twice annd this will keep happening till it reaches the base condition. So, it looks similar to a binary tree (as shown in the image). Now, the issue is that the last 2 nodes of that tree are not being executed by the compiler.

Let me try to elaborate a bit on it. I will try to tell how the function executes and creates the stack but I will be mainly focusing on the 2nd call which is sub(ros,ans+ch) and ignore the first call which is sub(ros,ans) because the problem is that the second last call of sub(ros,ans+ch) is not being executed.

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

The sub("BC","A") will call 2 functions that are sub("C","A") and sub("BC","AB"). Lets ignore the first call again.

sub("BC","AB") will call sub("C","AB") and sub("C","ABB"). Ignoring the first call again means:

sub("C","ABB") will call sub("","ABB") and sub("","ABBC").

These 2 calls will reach the base case and should print ABB and ABBC at the end of the program but it is not happening.

According to the stack, the output is correct but it should have another 2 lines of output containing strings ABB and ABBC which is not happening. I have checked the stack execution multiple times since last 24 hours and I don't see any problem with that. Any help is appreciated, thanks.

c++14 c++17 c++11 visual-c++ c++
1 Answers

You can instrument the function to see more clearly what happens:

#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;
}

Output is:

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","").

Correct.

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").

Wrong.

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

sub("BC","A") calls sub("C","A") and sub("C","AB").

user_41177280
Related