Stack overflow or tail recursion?

Question

I'm trying to find out if the following code piece is good or bad practice. It's about a html query string that should be parsed by my API. It's very convenient to use recursion to trim an arbitrary amount of '?' off the query string.

However, I'm wondering if this could potentially result in a stack overflow due to the uncontrollable recursion depth. My hope is that such cases are guaranteed to be tail-optimized but I'm not sure about it. Is there such guarantee?

Demo

#include <string_view>
#include <cstdio>

static auto digest_query(std::string_view query) -> void
{
    if (query.front() == '?') {
        // printf("%.*s\n", (int)query.size(), query.data());
        return digest_query(query.substr(1));
    }
    // Do other stuff...
}

int main()
{
    digest_query("???????key=value");
}

any code that is could be tail-recursion optimised (note that there is no guarantee this'll happen) can be replaced with a loop. stackoverflow.com/questions/34125/… — Alan Birtles
– Alan Birtles, Commented Feb 10, 2023 at 8:09
There are no such guarantees in C++. It's also a bit tricky to ensure that function calls are in tail position in C++ due to the presence of destructors. — molbdnilo
– molbdnilo, Commented Feb 10, 2023 at 8:17
If my edit is ok, then this looks like a duplicate: stackoverflow.com/questions/34125/… edit: or not, because its only about the possibility not about the guarantee — 463035818_is_not_an_ai
– 463035818_is_not_an_ai, Commented Feb 10, 2023 at 8:32
@463035818_is_not_a_number I am willing to grant "grey" in this case because the author did single out a concern about stack overflow. If it was just about good/bad design, yes it is opinion-based. But when the question comes with an objective criterion for good/bad, there might be a basis for answers that are more than just opinion-based. In this case... well, the question's been changed, so the issue is moot. :) — JaMiT
– JaMiT, Commented Feb 10, 2023 at 8:38
You may want to present your code on codereview.stackexchange.com, too. It looks horribly inefficient to me to repeatedly copy that string. — Ulrich Eckhardt
– Ulrich Eckhardt, Commented Feb 10, 2023 at 8:54

n. m. could be an AI · Accepted Answer · 2023-02-10 09:11:04Z

2

Is there such guarantee?

No there isn't.

answered Feb 10, 2023 at 9:11

n. m. could be an AI

122k14 gold badges141 silver badges267 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

user1196549 · Accepted Answer · 2023-02-10 09:16:04Z

0

The recursion depth is not "uncontrolled", it is exactly equal to the number of leading '?'. Every level will host a string variable on the stack, but the string data itself is allocated on the heap.

So there is absolutely no risk of overflow, but this code is so inefficient ! It will involve - recursive calls, - string allocation/deallocations, - string copies. All of this perfectly useless. I call it disaster.

Should I add that I find it pretty unreadable (so unexpected) compared to a regex query or a straightforward loop ?

answered Feb 10, 2023 at 9:16

user1196549

13 Comments

n. m. could be an AI Over a year ago

"it is exactly equal to the number of leading '?'" Which is uncontrolled. "string allocation/deallocations" There are no string allocations or deallocations in this fragment.

user1196549 Over a year ago

@n.m.: wrong: substring returns a newly constructed string object with its value initialized to a copy of a substring of this object.

n. m. could be an AI Over a year ago

There are no strings here, only string views.

user1196549 Over a year ago

@n.m.: I missed that, my bad. That lessens my diatribe.

Konrad Rudolph Over a year ago

@YvesDaoust Oh I see. Alright. I agree with this point actually. I thought your entire comment was responding to the "arbitrary large [user] input". At any rate, my comment stands as a response to that part: this is a potential exploit vector if user input can crash the application or cause UB via stack overflow.

|

Collectives™ on Stack Overflow

Stack overflow or tail recursion?

2 Answers 2

Comments

13 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

13 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related