Recursive function building a vector, what will be returned?

Question

so I'm trying to build a vector recursively, as I look at this I begin to think I'm doing it quite wrong. Will the following code return a vector with each iterations results, or am I just creating new vectors on each iteration that actually wont build on each recursive call. If I'm wrong, how do I go about building a vector recursively... Thanks in advance for your constructive help!

std::vector<ParameterClass> recursiveParser :: parseParamList() { std::vector<ParameterClass> paramVector; if (lexicator->getCurrentToken()->getTokenType() == STRING) { paramVector.push_back(ParameterClass(*lexicator->getCurrentToken())); lexicator->advance(); parseParamList(); } else if (lexicator->getCurrentToken()->getTokenType() == ID) { paramVector.push_back(ParameterClass(*lexicator->getCurrentToken())); lexicator->advance(); parseParamList(); } else { // so as to not fail in Expression, i need to check to see that there is a // left paren indicating that there should be an expression if (lexicator->getCurrentToken()->getTokenType() == LEFT_PAREN) { paramVector.push_back(ParameterClass(parseExpression())); lexicator->advance(); parseParamList(); } } return paramVector; }

why don't you combine 1st and 2nd condition into one? looks redundant — mangusta
– mangusta, Commented Apr 9, 2014 at 6:04

Spook · Accepted Answer · 2014-04-09 06:18:54Z

If you want build a list (vector etc) recursively, use the following pattern:

private: void InternalBuild(std::vector<OutputData> & vec) { // Add data to vec // Possibly call recursively InternalBuild(vec); } public: std::vector<OutputData> RecursiveBuild() { std::vector<OutputData> vec; InternalBuild(vec); return vec; }

It is worth noting, that you seem to misuse recursion here. The recursion is meant to be used on data structures, which are recursive by their nature (trees, graphs etc.). In this case you process linear data recursively - why not simply write something like:

while (!lexer.endOfExpression()) { // Process token lexer.Advance(); }

In your case, if you get expression long enough, you'll end up with a stack overflow exception, because your program will run out of stack memory. That won't happen if you implement this algorithm linearly.

Thanks for the Input! Your right about the linearity of this problem, however I have other portions of the program that are recursive in nature, I've just been modeling my classes the same.
I re-wrote my recursive calls using the method you explained, it makes sense, and worked like a charm!
Is there any performance penalty to passing a vector reference through recursive calls?
@KevinLeeGarner If you pass a std::vector by reference (as I do), internally it equals to passing a pointer (4 bytes), so this is neither memory nor time-costly.

Bryan Chen · Accepted Answer · 2014-04-09 06:11:37Z

try this, which append the result from recursive call

 std::vector<ParameterClass> recursiveParser :: parseParamList() { std::vector<ParameterClass> paramVector; if(lexicator->getCurrentToken()->getTokenType() == STRING) { paramVector.push_back(ParameterClass(*lexicator->getCurrentToken())); lexicator->advance(); std::vector<ParameterClass> result = parseParamList(); std::copy(result.begin(), result.end(), std::back_inserter(paramVector)); } else if(lexicator->getCurrentToken()->getTokenType() == ID) { paramVector.push_back(ParameterClass(*lexicator->getCurrentToken())); lexicator->advance(); std::vector<ParameterClass> result = parseParamList(); std::copy(result.begin(), result.end(), std::back_inserter(paramVector)); }else { // so as to not fail in Expression, i need to check to see that there is a left paren indicating that there should be an expression if(lexicator->getCurrentToken()->getTokenType() == LEFT_PAREN) { paramVector.push_back(ParameterClass(parseExpression())); lexicator->advance(); std::vector<ParameterClass> result = parseParamList(); std::copy(result.begin(), result.end(), std::back_inserter(paramVector)); } } return paramVector; }

also please use switch instead of if-elseif-elseif and avoid repeated code

std::vector<ParameterClass> recursiveParser :: parseParamList() { std::vector<ParameterClass> paramVector; switch(lexicator->getCurrentToken()->getTokenType()) { case STRING: paramVector.push_back(ParameterClass(*lexicator->getCurrentToken())); break; case ID: paramVector.push_back(ParameterClass(*lexicator->getCurrentToken())); break; case LEFT_PAREN: // so as to not fail in Expression, i need to check to see that there is a left paren indicating that there should be an expression paramVector.push_back(ParameterClass(parseExpression())); break; } lexicator->advance(); std::vector<ParameterClass> result = parseParamList(); std::copy(result.begin(), result.end(), std::back_inserter(paramVector)); return paramVector; }

but use @Spook's pattern, because it allows tail call optimization

Collectives™ on Stack Overflow

Recursive function building a vector, what will be returned?

2 Answers 2

4 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Related