Editing Recursion

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

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]]
Warning: This article is a work in progress! No refunds if it moves!
[[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==
- introduction/overview
Recursion can create loops without language constructs.
 
Here's an infinite loop:
function infinite_loop()
  print("Hello there!")
  return infinite_loop()
end
infinite_loop()


This is a bit longer than a non-recursive example.
- 'magic of recursion'?


Here's a counting loop:
- lua
function count_down(number)
  if number == 0 then return end
  print(number)
  return count_down(number - 1)
end
count_down(100)


A non-recursive version of this would likely use some kind of for or while loop.
==Example==
Most introductions to recursion I've seen use this Fibonacci gem:


Here's a loop that asks a user to pick a valid choice:
  function fib(n)
  function get_choice(choices)
   if n <= 1 then
   local line = io.read()
     return n
  choice = choices[line]
  if choice then
     return choice
   else
   else
     print("Invalid choice! Try again")
     return fib(n - 1) + fib(n - 2)
    return get_choice(choices)
   end
   end
  end
  end
  print("Select a letter to get a number: A, B, C")
 
choice = get_choice({A=1, B=2, C=3})
  print(fib(41))
print("You picked number " .. choice)
-- prints 165580141
Without recursion this code would look a lot more confusing, at least to me.
This code is confusing to me and to my computer. This ends up causing severe speed penalities:
 
*fib(38) takes 6 seconds on my computer
*fib(39) takes 10 seconds on my computer
*fib(40) takes 17 seconds on my computer
*fib(41) takes 30 seconds on my computer
 
fib(41) effectively takes 13 seconds to add 102334155 and 63245986 together. Ridiculous.
 
The issue here is that each step re-calculates all previous steps. Twice even!


==State machines==
An equivalent version without recursion is:
Not all recursion has to be direct. Indirect recursion lets you represent state machines easily.


Here's a tiny adventure game with the player choosing state transitions:
  function fib(n)
  function dark_room()
   if n <= 1 then
  print("You are in a dark room.")
    return 1
  print("Pick a door: fuzzy or metal")
  choice = get_choice({fuzzy=1, metal=2})
   if choice == 1 then return fuzzy_room()
  elseif choice == 2 then return metal_room()
   end
   end
end
   a, b = 0, 1
function fuzzy_room()
   for i = n, 1, -1 do
   print("This room feels pretty fuzzy...")
    a, b = b, a + b
  print("Pick a door: dark, metal")
   choice = get_choice({dark=1, metal=2})
  if choice == 1 then return dark_room()
  elseif choice == 2 then return metal_room()
   end
   end
  return a
  end
  end
  function metal_room()
   
  print("This room feels really metallic.")
print(fib(41))
  print("Pick a door: dark, fuzzy or win")
-- prints 165580141
  choice = get_choice({dark=1, fuzzy=2, win=3})
 
   if choice == 1 then return dark_room()
This runs instantly on my machine. fib(100000000) takes 6 seconds on my computer.
   elseif choice == 2 then return fuzzy_room()
 
  elseif choice == 3 then return metal_room()
At this point the impression you would get is that recursion is slow and ill suited for these tasks. Not so fast!
 
We can modify the example to store the previous two steps in the 'a' and 'b' function arguments:
function fib(n, a, b)
   if n <= 1 then
    return b
   else
    return fib(n - 1, b, a + b)
   end
   end
  end
  end
  function win_room()
   
  print("You found the treasure!")
print(fib(41, 0, 1))
  return
-- prints 165580141
end
 
dark_room()
This version is just as fast as the iterative solution, it's just written recursively.
Without recursion you'd likely need to put everything in a single function with a loop and state variable.
 
- mention stack overflow
 
- imagine an infinite stack
 
==Loops==
- recursion can implement loops!
 
- implementing a for loop
 
- implementing a while loop
 
- implementing a do while loop
 
- each loop iteration only shares global and function args
 
==State machines==
- implementing a stateful algorithm
 
- some kind of menu system
 
- the code makes sense to read
 
- this is mutual recursion
 
- very hard to do in a traditional structured language


Some things just make more sense when implemented recursively, to me at least.
==Lambdas==
- lambdas to actually replace looping constructs/switch statements


== Tail call optimization ==
- most mainstream languages support lambas
There is a caveat with recursive programs: Each function call takes up stack space. The deeper you recurse, 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 that return call is a 'tail call'. Languages that implement tail call optimization will re-use the current function call's stack for the function you're calling, solving the issue of stack space.
- recursion-based control flow


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.
==Tail call elimination==
- floating back down to reality


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 shout-out to the folks at Wikisource that transcribed this to an accessible text form.
- we've been writing code as there's no stack


The significant downside of tail call optimization from a user perspective is that it can make debugging more difficult as you lack a proper stack trace.
- tail call elimination


From an implementer perspective the problem is that stack cleanup is tricky: A function that tail calls another cannot clean up any temporary variables it passes along. The solution to this is to make sure function stack use is identical and have the caller clean up, or to implement garbage collection.
- NOT an optimization, how many optimizations decide which way you can program?


==Language support==
- hints deeper at function calls vs jumps
Despite 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 automatically:
- structured programming, goto wars


* Haskell
==Mainstream support==
* Erlang (and Elixir)
- functional programming languages
*Any Scheme implementation (Chez Scheme, Chibi Scheme, Chicken Scheme, TinyScheme)
*Lua (see [https://www.lua.org/pil/6.3.html Programming in Lua 6.3 - Proper Tail Calls])
*Steel Bank Common Lisp (See [http://www.sbcl.org/manual/#Debug-Tail-Recursion SBCL Debug Tail Recursion])
*Squirrel (See [http://squirrel-lang.org/squirreldoc/reference/language/threads.html Squirrel's Threads page])
*Racket (See [https://docs.racket-lang.org/guide/Lists__Iteration__and_Recursion.html#%28part._tail-recursion%29 The Racket Guide 2.3.3 - Tail Recursion])
Here's an incomplete list of languages that require explicit support:
* Clang C and C++ (see the [https://clang.llvm.org/docs/AttributeReference.html#musttail Clang musttail attribute])
* Tcl (see [https://www.tcl.tk/man/tcl/TclCmd/tailcall.html Tcl's tailcall manual page])
*OCaml (See [https://ocaml.org/manual/attributes.html OCaml's tailcall attribute])
* Perl (See [https://perldoc.perl.org/functions/goto Perl's goto function], specifically the goto &NAME variant)
*Unix (See [https://jeapostrophe.github.io/2012-05-28-exec-vs--post.html exec and Tail-call Optimization])
*Assembly (Instead of returning set up registers and jump)
*Ruby (See [https://nithinbekal.com/posts/ruby-tco/ Ruby's tailcall_optimization compile option])
*Zig (See [https://ziglang.org/documentation/master/#call Zig's always_tail call option])


Here's an incomplete list of popular languages that don't support it:
- lua


* C and C++
- clang mustcall
* Go
* Rust
* Swift
* PHP
*Python
*Raku
* Anything running on the JVM (Java, Clojure, Scala, Kotlin)
* Anything running on .NET (C#, F#)
* Anything running on WebAssembly
* Anything JavaScript or transpiling to JavaScript (TypeScript, CoffeeScript)
Things look decent for desktops, but not so much for phones or web browsers.


Personally I lean towards the idea of languages adding new keywords or explicit support for this, such as a 'goto' or 'jump' keyword. It helps in a debugger when you have stack frames by default, and it helps make it clear that it's important that this tail call is optimized.
- webassembly
Please note that all contributions to JookWiki are considered to be released under the Creative Commons Zero (Public Domain) (see JookWiki:Copyrights for details). If you do not want your writing to be edited mercilessly and redistributed at will, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource. Do not submit copyrighted work without permission!

To edit this page, please answer the question that appears below (more info):

Cancel Editing help (opens in new window)
Retrieved from "https://www.jookia.org/wiki/Recursion"