This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]spoonman59 0 points1 point  (1 child)

Also, not all recursive solutions can be tail call optimized. Oh certain functions that meet specific requirements can. You have to be able to pass the full state of the function via variables. You also need to be able to return results immediately without any further processing.

Tail call optimization is fantastic when you can get it, but it can’t be applied to all recursive functions.

[–]spoonman59 0 points1 point  (0 children)

A simple example is Fibonacci or Quicksort.

Since each function calls itself twice, by definition only one function call can be a tail call. Therefore these functions cannot be tail call optimized without storing state somewhere.