Tracing this recursive code

Question

The code below is my book and I need to trace its execution, showing the stack frame created for each recursive call, the values stored in the stack frame, and the value returned. Where I am confused is in line 17 behead(s+1,n-1) because s is a string variable so how it is possible to add it an integer. I could not run this code because of this detail.

#define Z 3 
string behead( string s, int n );

int main( void )
{
    string answer;
    char word[] = "distrust";
    printf( "\nBeheading the victim: %s?\n", word );
    answer = behead( word, Z );
    printf( "Now: %s!\n\n", answer );
}

string behead( string s, int n )
{
    if (n == 0) return s;
    else return behead( s + 1, n - 1 );
}

I guess the code initially used 'char *' instead of 'string' and you wanted to improve it, is that right? — piokuc
– piokuc, Commented Nov 27, 2012 at 17:53
First off, the Homework tag is obsolete. Second, do they define a string class anywhere (either way you seem to be missing includes)? Plus, this code looks pretty bad for C++. — crashmstr
– crashmstr, Commented Nov 27, 2012 at 17:54
Are we to assume (a) #include <cstdio>, #include <string> and using namespace std; ? Apart from that, I can tell you what this will do: not compile, as std::string has no operator +(int) that I'm aware of, assuming you're using std::string. If you're not, we can't answer this without knowing the definition of what your string class is. — WhozCraig
– WhozCraig, Commented Nov 27, 2012 at 17:56
The book says that this code makes some string manipulation but it does not specify the headers so I assume they might be #include <stdio.h> #include <string> and using namespace std; This was my first thought but like Whozcraig said it will not complie. — user1678927
– user1678927, Commented Nov 27, 2012 at 18:04

WhozCraig · Accepted Answer · 2012-11-27 18:20:49Z

I think the person that ported this did so with total disregard for an end-goal of something that actually compiled. It looks like a C-recursive function that was ill-ported and never tested/compiled. It is likely they wanted something like this:

#include <string>
#include <cstdio>
using namespace std;


#define Z 3 
string behead( string s, int n );

int main( void )
{
    string answer;
    char word[] = "distrust";
    printf( "\nBeheading the victim: %s?\n", word );
    answer = behead( word, Z );
    printf( "Now: %s!\n\n", answer.c_str() );
}

string behead( string s, int n )
{
    if (n == 0) return s;
    return behead(s.substr(1), n-1);
}

Note the c_str() in the printf argument list, another defect in the original code.

You asked what this does: it recursively pulls one char from the start of the input string, repeating until n chars have been pulled. A call stack of this through the final return would be as follows, where s"..." denotes a std::string object by-value:

behead(s"distrust", 3)
   behead(s"istrust", 2)
      behead(s"strust", 1)
         behead(s"trust", 0)  <<== return point.

It is also utterly useless, as this:

string word = "distrust";
string answer = word.substr(Z);

accomplishes the same thing without the recursion (and is a helluva lot clearer).

Collectives™ on Stack Overflow

Tracing this recursive code

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related