Skip to Main Content

Implement tail recursion elimination in PL/SQL

Zlatko SiroticApr 18 2015 — edited Jan 11 2016

Very often, a recursive algorithm is more elegant and concise than a loop-based one (imperative).

But in PL/SQL, the imperative approach is more efficient, and safer (because it can not cause a stack overflow).

A tail call is a procedure (or a function) call performed as the final action of a procedure.

Tail calls can be implemented without adding a new stack frame to the call stack - this is known as the tail call elimination (or optimization).

Tail recursion elimination is a special case of tail call elimination, where the tail call is to the procedure itself.

A tail-recursive procedure will not build a new stack frame for each call; all calls will execute in a single frame.

Tail call elimination (including tail recursion elimination) is implemented in virtually all functional languages.

But there are some imperative languages that also have this optimization, eg. C# and Scala (Scala is not only imperative language, but also (incomplete) functional language).

Perhaps this optimization will be introduced in Java too.

Brian Goetz (Java Language Architect at Oracle) in this video:

https://www.youtube.com/watch?v=2y5Pv4yN0b0&t=1h02m18s

mentions that it is not a priority, but that tail recursion elimination will eventually get done.

Comments
Post Details
Added on Apr 18 2015
0 comments
649 views