CODEWITHSUNDEEP
c++visual-studio-2010
user1678927
user1678927

Reputation: 25

Tracing this recursive code

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

Upvotes: 1

Views: 96

Answers (1)

WhozCraig
WhozCraig

Reputation: 66214

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

Upvotes: 2

Related Questions