Editing Recursion
The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then publish the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 1: | Line 1: | ||
[[Category:Research]] | [[Category:Research]] | ||
Recursion is a fantastic and often ignored feature of programming languages. Most introductions show an example you'd never use in practice, so this article is my attempt at showing some better ones using Lua. | |||
==Loops== | ==Loops== | ||
Line 47: | Line 47: | ||
print("You are in a dark room.") | print("You are in a dark room.") | ||
print("Pick a door: fuzzy or metal") | print("Pick a door: fuzzy or metal") | ||
choice = get_choice({fuzzy=1, metal=2}) | choice = get_choice({fuzzy=1,metal=2}) | ||
if choice == 1 then return fuzzy_room() | if choice == 1 then return fuzzy_room() | ||
elseif choice == 2 then return metal_room() | elseif choice == 2 then return metal_room() | ||
Line 55: | Line 55: | ||
print("This room feels pretty fuzzy...") | print("This room feels pretty fuzzy...") | ||
print("Pick a door: dark, metal") | print("Pick a door: dark, metal") | ||
choice = get_choice({dark=1, metal=2}) | choice = get_choice({dark=1,metal=2}) | ||
if choice == 1 then return dark_room() | if choice == 1 then return dark_room() | ||
elseif choice == 2 then return metal_room() | elseif choice == 2 then return metal_room() | ||
Line 79: | Line 79: | ||
== Tail call optimization == | == Tail call optimization == | ||
There is a caveat with recursive programs: Each function call takes up stack space. The deeper you | There is a caveat with recursive programs: Each function call takes up stack space. The deeper you recursive, the more likely you are to run out of stack space and crash your program. This makes recursion useless in most programming languages. | ||
However there is a compromise: If a return in a function is just a call to another function then | However there is a compromise: If a return in a function is just a call to another function then return is a 'tail call'. Languages that implement tail call optimization will re-use the current function call's stack for the tail call, solving the issue of stack space. | ||
All the examples on this page use tail calls and run in Lua which implements tail call optimization. This means every program on this page is immune to stack overflows. | All the examples on this page use tail calls and run in Lua which implements tail call optimization. This means every program on this page is immune to stack overflows. | ||
The 1977 [https://en.wikisource.org/wiki/Index:AIM-443.djvu AI Lab Memo 443] talks more broadly about how tail calls are like goto statements that you can pass arguments to. Huge | The 1977 [https://en.wikisource.org/wiki/Index:AIM-443.djvu AI Lab Memo 443] talks more broadly about how tail calls are like goto statements that you can pass arguments to. Huge shoutout to the folks at Wikisource that transcribed this to an accessible text form. | ||
==Mainstream support== | |||
Despite mainstream languages slowly adding features from functional languages developed 40 years ago, tail call optimization is still unpopular. I'm guessing that the reason is because not many people see the use of recursion. | |||
Here's an incomplete list of languages that support it: | |||
Here's an incomplete list of languages that support it | |||
* Lua (see [https://www.lua.org/pil/6.3.html Programming in Lua 6.3 - Proper Tail Calls]) | |||
* Clang C and C++ (see the [https://clang.llvm.org/docs/AttributeReference.html#musttail musttail attribute]) | |||
* Tcl (see Tcl's [https://www.tcl.tk/man/tcl/TclCmd/tailcall.html tailcall manual page]) | |||
* Haskell | * Haskell | ||
* Erlang (and Elixir) | * Erlang (and Elixir) | ||
Here's an incomplete list of popular languages that don't support it: | Here's an incomplete list of popular languages that don't support it: | ||
Line 119: | Line 104: | ||
* Rust | * Rust | ||
* Swift | * Swift | ||
* Perl | |||
* PHP | * PHP | ||
* Anything running on the JVM (Java, Clojure, Scala, Kotlin) | * Anything running on the JVM (Java, Clojure, Scala, Kotlin) | ||
* Anything running on .NET (C#, F#) | * Anything running on .NET (C#, F#) | ||
* Anything running on WebAssembly | * Anything running on WebAssembly | ||
* Anything JavaScript or transpiling to JavaScript (TypeScript, CoffeeScript) | * Anything JavaScript or transpiling to JavaScript (TypeScript, CoffeeScript) | ||