Recursion: Difference between revisions

From JookWiki
(→‎Loops: Note we don't need language constructs)
(Add tail call optimization section)
Line 1: Line 1:
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.
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 74: Line 74:
  dark_room()
  dark_room()
Without recursion you'd likely need to put everything in a single function with a loop and state variable.
Without recursion you'd likely need to put everything in a single function with a loop and state variable.
== Tail call optimization ==
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 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.


==Mainstream support==
==Mainstream support==
- structured programming
- functional programming languages
- functional programming languages



Revision as of 05:03, 3 February 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.

Tail call optimization

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

Mainstream support

- structured programming

- functional programming languages

- lua

- clang mustcall

- webassembly