Is this the most efficient code?

[jjordan33]

Hi, I'm doing some study, and one topic is making a recursive function to print this:
****
***
**
*

Is my code the best way to do this?

#include <iostream>
#include <string>

using namespace std; 

void printAst(string ast){
	if (ast == ""){
		return;
	}

	cout << ast << endl;
	
	ast = ast.substr(0, ast.length()-1);
	
	printAst(ast);

}

int main(){

	string temp = "****";
	
	printAst(temp);

	return 0;
}

Thank you.

[lastchance]

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

string triangle( int n )
{
   return n ? string( n, '*' ) + '\n' + triangle( n - 1) : "\n";
}

int main()
{
   cout << triangle( 4 );
}

[jjordan33]

lastchance,

You took it from 26 to 13 lines with the same libraries. I'd definitely say that was more efficient. Thanks a lot.

[lastchance]

No, your own code is fine. And it would cover more complex strings like "*£&^%" where there is no repeating character.

In the end, "more efficient" probably means having taken the time to write and understand your own stuff. So yours is good.

[jjordan33]

That's a good point.

Still though, I didn't even think about being able to add or subtract from the parameter inside the recursive call yet(I just started on recursion, and it's hard to wrap my mind around how they seem to almost work from both ends and meet in the middle), so that simultaneously opens up new possibilities for me and sets me back about 2 days of understanding lol.

Thank you.

[MikeStgt]

I try to avoid the last (empty) line but fail. How may I filter it in main()? IMO four lines would be enough for printTriangle( 4 ).

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

string printTriangle( int n )
{
   return n ? string( n, '*' ) + '\n' + printTriangle( n - 1) : "\0";
}

int main()
{
   cout << printTriangle( 4 );
   cout << "<<< End of last line is here.";
}

Edit:
Reult from the code above is

****
***
**
*
<<< End of last line is here. 

Solved my requirement (remove empty line) like this:

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

string printTriangle( int n )
{
   return (n-1) ? string( n, '*' ) + '\n' + printTriangle( n - 1) : "*";
}

int main()
{
   cout << printTriangle( 4 );
   cout << "<<< End of last line is here.";
}

Result now:

****
***
**
*<<< End of last line is here.

[jjordan33]

Mike,

You could just do a failsafe check after line 6 in lastchance's code.

if (n == 1){
return "*";
}

[JLBorges]

> Is this the most efficient code?

Assuming that we do not want pass objects by reference to recursive functions,
avoiding creation of temporary strings, and moving rather than copying strings may be more (machine) efficient.

#include <iostream>
#include <string>

void printAst( std::string ast ) {

    if( !ast.empty() ) {

        std::cout << ast << '\n' ;

        ast.pop_back() ; // knock off the last character O(1)

        printAst( std::move(ast) ) ; // and avoid a deep copy
    }
}

int main() {

	printAst( "********************************" );
}

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

[jjordan33]

JLBorges,

Will every stackoverflow check be an if statement? I've never seen anyone use a while for it.

Thank you.

[MikeStgt]

You could just do a failsafe check after line 6 in lastchance's code.

Something similar was my first idea too, prevent the last call to printTriangle(). Alas it would disturb the elegance of the {(test)? (if true) : (if not)} construct.

[lastchance]

For @MikeStgt:
return n ? string( n, '*' ) + '\n' + triangle( n - 1) : "";

[JLBorges]

> Will every stackoverflow check be an if statement?

I suppose you mean checking for the base (termination) case(s).
Yes, it would typically be done with a conditional statement.

[MikeStgt]

How about:
return (n-1) ? string( n, '*' ) + '\n' + triangle( n - 1) : "*";

[jjordan33]

Oh, that's what it's called?

Thank you kindly.

[keskiverto]

Will every stackoverflow check be an if statement? I've never seen anyone use a while for it.

Consider a tree. Each node has a list of children. (Leaf nodes have empty list.)

walk( Node* root ) {
  // do something with root
  for ( auto child : root->children ) {
    walk( child );
  }
  // do something with root
}

Yes, you could have if ( root->children.empty() ) there too, but if you do iterate children (rather than recurse) and it does suffice to "not recurse" on leaf, then you might see a loop.