Converting iterative to recursive function

[btoohey4]

I have to write a recursive function called void recursive_call(int call)
based off an iterative function, that I need to convert to a recursive function that prints the exact following output:

This was written by call number 1
 This was written by call number 2
  This was written by call number 3
   This was written by call number 4
   This was written by call number 4
  This was written by call number 3
 This was written by call number 2
This was written by call number 1

This is the working iterative function for this:

void iterative_call()
{
int call = 1;
string statement = "This was written by call number ";
for (; call != 5; ++call) {
cout << statement << call << endl;
statement = " " + statement; // adds leading white space
}
for (--call; call != 0; --call)
cout << statement.erase(0,1) << call << endl; // removes leading white space
}

Any help with how to convert it would be fantastic. I know I can't use loops, and will have to call recursive_call(call++) but I'm not sure how to get this working.
Thanks!

[MrHutch]

Think of the properties of recursive methods:

1) They need to have a base case. This is the point at which your logic breaks out of the recursion. In your case, the base case is when call == 4.

2) They need to operate on subproblems or values that approach that base case. In your case, this is achieved by adding one the the argument for the next recursive call.

Give those two properties, how do you think you'd go about writing this? If you provide some code, it's easier to lend a hand on the parts you're struggling with.

[keskiverto]

What if a function prints the same line twice, but calls itself in between the printouts?


Edit: Look at your sample output. Isn't that a strong hint about who writes what?

[btoohey4]

@iHutch105 I would like to say I now understand, but the fact that it has to go up to 4 and then back down is really throwing me off. I don't have much clue about all how to start other than that if statements are needed.

[MrHutch]

btoohey4 wrote:

the fact that it has to go up to 4 and then back down is really throwing me off

keskiverto's suggestion would solve that. Incidentally, I did the same thing for my implementation.

[btoohey4]

@iHutch105
Obviously not following the specs, but I have rigged up this program that prints up to whatever number you have. So if I called recursive_call(5) this currently prints 0, 1, 2, 3, 4, 5. Is this at all on the right track?

void recursive_call(int call) {
	string statement = "This was written by call number ";

	if (call > 0) {
		recursive_call(-call + 1);
		cout << call << endl;
	}
	else if (call == 0) {
		cout << call << endl;
	}
	else {
		recursive_call(call + 1);
		cout << -call << endl;
	}
}

[MrHutch]

It's getting there. I'd go more along the lines of:

print statement

if call < 4
   recursive_call(call + 1)

print statement

[btoohey4]

@iHutch105
The trouble I'm having is the reverse, my current code (below) prints 1 2 3 4 3. I know that it cannot go down further as it hits (call < 4) and then adds again. So I'm wondering if you have any tips on how I'm supposed to make it double the four and then continuously go back to 1? Thanks!

#include <iostream>
using namespace std;

void recursive_call(int call) {
	string statement = "This was written by call number ";

	cout << call << endl;

	if (call < 4) {
		recursive_call(call + 1);
		cout << call << endl;
	}

	else {
		recursive_call(call - 1);
		cout << call << endl;
	}


}

int main()
{
	recursive_call(1);
	return 0;
}

[MrHutch]

Why do you need that else clause?

What would happen if you replaced with the entire else clause with the code on line 7?

Do you think the std::cout call within the if statement is necessary?

Consider how recursive functions work in terms of the callstack and what happens when you reach the end of a function's scope.

[btoohey4]

@iHutch105 Thanks so much! I just need to figure out how to add in the appropriate white spaces to convey the step down and back up and I'll be done

[MrHutch]

Awesome. Glad you're there.

Happy to share my implementation now. :-)

https://ideone.com/y9Ecpz

It's a bit naive in that it's centred towards your use case (for e.g, if you run recursive_call(5) you'd eventually get a stack overflow).

[D80DSL3A]

I solved the adding spaces problem by passing the message as a function argument:

recursive_call( string msg,  int call)
{
    // something
    if( call < 4 ) recursive_call( ' ' + msg,  1 + call);// increment both arguments
    // something more
}

[keskiverto]

One could also use std::setw from <iomanip> to add prefix spaces. (The default fill character is space.)

Appending a prefix to a string is probably more costly than appending at the end.

Functions can have default values for their arguments:

void recursive_call( int call, std::string prefix = "" ) {
  prefix.reserve( 3 ); // memory allocation optimization
  // something
  if ( call < 4 ) recursive_call( 1 + call, prefix + ' ' );
  // something
}

int main() {
  recursive_call( 1 ); // real arguments are ( 1, "" )
  return 0;
}

[btoohey4]

@iHutch105 @fun2code @keskiverto
Is there possibly any way of doing this that doesn't involve either loops or altering the function arguments?

[D80DSL3A]

Not that I can think of.
Those are some very severe restrictions you just casually threw down on the possible solution methods.
Good luck!

[keskiverto]

The std::setw. Does
if ( 1 < call ) std::cout << std::setw( call - 1 ) << ' ';
look like a loop?

[D80DSL3A]

edit: sorry. I was thinking 'can't alter the arguments values' not 'can't alter the argument list'.

Also, I forgot that static local variables can ve useful in recursive functions for transmitting state across recursion levels. Is that fair game?
Consider this version. It takes 1 integer argument as required.

void showSteps( int call = 1 )
{
    const std::string msg("call #");
    static std::string spaces;

    cout << spaces << msg << call << '\n';
     spaces += ' ';
    if( call < 4 ) showSteps( call + 1 );
    spaces.pop_back();
    cout << spaces << msg << call << '\n';

    return;
}

@keskiverto How does your std::setw use work? I tried and got nowhere with that.

[JLBorges]

void zig_zag( unsigned int n = 0 )
{
    if( n < 4 )
    {
        std::cout << std::string( n, ' ' ) << "This was written by call number " << n+1 << '\n' ;
        zig_zag(n+1) ;
        std::cout << std::string( n, ' ' ) << "This was written by call number " << n+1 << '\n' ;
    }
}

The version using the manipulator is somewhat clumsier (requires extra if statements):

void zig_zag2( unsigned int n = 0 )
{
    if( n < 4 )
    {
        if( n > 0 ) std::cout << std::setw(n) << ' ' ;
        std::cout << "This was written by call number " << n+1 << '\n' ;
        zig_zag(n+1) ;
        if( n > 0 ) std::cout << std::setw(n) << ' ' ;
        std::cout << "This was written by call number " << n+1 << '\n' ;
    }
}

http://coliru.stacked-crooked.com/a/c9e788c2fc1ac855