Is there a recursive function / algorithm where using stack frames is unavoidable (cannot be made fully tail recursive)?

Question

I'm trying to come up with examples of recursive algorithms / functions that cannot be rewritten in a way that avoids using lots of stack memory (i.e. cannot be made fully tail recursive nor rewritten using a loop that doesn't use a stack). Do such functions exist?

I think quicksort might be a candidate, but am not sure if it can be rewritten to use a single tail-recursive function call.

This question is more appropriate for cs.stackexchange.com

bengoesboom
– bengoesboom

2013-09-19 04:21:19 +00:00
Commented Sep 19, 2013 at 4:21 — bengoesboom
– bengoesboom, Commented Sep 19, 2013 at 4:21
Try Ackermann function.

Aki Suihkonen
– Aki Suihkonen

2013-09-19 04:44:09 +00:00
Commented Sep 19, 2013 at 4:44 — Aki Suihkonen
– Aki Suihkonen, Commented Sep 19, 2013 at 4:44

Sylwester · Accepted Answer · 2013-09-19 06:56:25Z

0

Every algorithm that requires more than one call in the general case cannnot be done without a backtrack stack for iteration or growing the stack because the first call is not in tail position and will always have a continuation.

The simple fibonacci, quicksort and sum of tree are all in that category.

answered Sep 19, 2013 at 6:56

Sylwester

48.9k4 gold badges52 silver badges83 bronze badges

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

Collectives™ on Stack Overflow

Is there a recursive function / algorithm where using stack frames is unavoidable (cannot be made fully tail recursive)?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related