Recursion: Difference between revisions

From JookWiki
(add tail call example)
(→‎Language support: Add personal opinion)
(31 intermediate revisions by the same user not shown)
Line 1: Line 1:
Warning: This article is a work in progress! No refunds if it moves!
[[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.


TODO: This article is about tail calls
==Loops==
Recursion can create loops without language constructs.


- introduction/overview
Here's an infinite loop:
function infinite_loop()
  print("Hello there!")
  return infinite_loop()
end
infinite_loop()


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


- lua
Here's a counting loop:
 
function count_down(number)
==Recursion==
  if number == 0 then return end
As a quick refresher, recursion is when code calls itself.
  print(number)
  return count_down(number - 1)
end
count_down(100)


Here's a textbook example:
A non-recursive version of this would likely use some kind of for or while loop.


  function fac(n)
Here's a loop that asks a user to pick a valid choice:
   if n < 1 then
  function get_choice(choices)
     return 1
  local line = io.read()
  choice = choices[line]
   if choice then
     return choice
   else
   else
     return n * fac(n - 1)
    print("Invalid choice! Try again")
     return get_choice(choices)
   end
   end
  end
  end
   
  print("Select a letter to get a number: A, B, C")
  print(fac(20))
choice = get_choice({A=1, B=2, C=3})
-- prints 2432902008176640000
  print("You picked number " .. choice)
Without recursion this code would look a lot more confusing, at least to me.


This code has a function 'fac' that takes a number and:
==State machines==
Not all recursion has to be direct. Indirect recursion lets you represent state machines easily.


* Returns 1 if the number is less than 1  
Here's a tiny adventure game with the player choosing state transitions:
* Calls fac with the number minus 1
function dark_room()
* Multiplies the result of fac by the number
  print("You are in a dark room.")
* Returns the multiplied result
  print("Pick a door: fuzzy or metal")
 
  choice = get_choice({fuzzy=1, metal=2})
Unfortunately there's a problem with this. When we call fac we need to save our current number so we can multiply it with the result of fac. If we recurse too many times we run out of memory on our stack to save our numbers.
  if choice == 1 then return fuzzy_room()
 
  elseif choice == 2 then return metal_room()
Because of this tendency to overflow the stack recursion isn't seen much in mainstream programming.
  end
 
end
==Tail calls==
function fuzzy_room()
What if we didn't need to save anything? We could recurse forever without any stack overflows.
  print("This room feels pretty fuzzy...")
 
  print("Pick a door: dark, metal")
Let's say we rewrite our factorial code to this:
  choice = get_choice({dark=1, metal=2})
function fac(n, acc)
  if choice == 1 then return dark_room()
   if n < 1 then
  elseif choice == 2 then return metal_room()
    return acc
  end
   else
end
    return fac(n - 1, acc * n)
function metal_room()
  print("This room feels really metallic.")
  print("Pick a door: dark, fuzzy or win")
  choice = get_choice({dark=1, fuzzy=2, win=3})
   if choice == 1 then return dark_room()
  elseif choice == 2 then return fuzzy_room()
   elseif choice == 3 then return metal_room()
   end
   end
  end
  end
   
  function win_room()
print(fac(20, 1))
  print("You found the treasure!")
  -- prints 2432902008176640000
  return
 
  end
- mention stack overflow
dark_room()
 
Without recursion you'd likely need to put everything in a single function with a loop and state variable.
- 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
 
==Lambdas==
- lambdas to actually replace looping constructs/switch statements


- most mainstream languages support lambas
Some things just make more sense when implemented recursively, to me at least.


- recursion-based control flow
== Tail call optimization ==
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.


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


- we've been writing code as there's no stack
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
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.


- NOT an optimization, how many optimizations decide which way you can program?
The significant downside of tail call optimization is that it can make debugging more difficult as you lack a proper stack trace.


- hints deeper at function calls vs jumps
==Language support==
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.


- structured programming, goto wars
Here's an incomplete list of languages that support it automatically:


==Mainstream support==
* Haskell
- functional programming languages
* Erlang (and Elixir)
*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])


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


- clang mustcall
* C and C++
* 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.


- webassembly
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.

Revision as of 06:29, 13 October 2022

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

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.

Here's a counting loop:

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.

Here's a loop that asks a user to pick a valid choice:

function get_choice(choices)
  local line = io.read()
  choice = choices[line]
  if choice then
    return choice
  else
    print("Invalid choice! Try again")
    return get_choice(choices)
  end
end
print("Select a letter to get a number: A, B, C")
choice = get_choice({A=1, B=2, C=3})
print("You picked number " .. choice)

Without recursion this code would look a lot more confusing, at least to me.

State machines

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 dark_room()
  print("You are in a dark room.")
  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
function fuzzy_room()
  print("This room feels pretty fuzzy...")
  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
function metal_room()
  print("This room feels really metallic.")
  print("Pick a door: dark, fuzzy or win")
  choice = get_choice({dark=1, fuzzy=2, win=3})
  if choice == 1 then return dark_room()
  elseif choice == 2 then return fuzzy_room()
  elseif choice == 3 then return metal_room()
  end
end
function win_room()
  print("You found the treasure!")
  return
end
dark_room()

Without recursion you'd likely need to put everything in a single function with a loop and state variable.

Some things just make more sense when implemented recursively, to me at least.

Tail call optimization

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.

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 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.

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

Language support

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:

Here's an incomplete list of languages that require explicit support:

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

  • C and C++
  • 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.