Recursion: Difference between revisions
(Save current page incarnation) |
(Add examples) |
||
Line 1: | Line 1: | ||
Warning: This article is a work in progress! No refunds if it moves! | 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. | |||
==Loops== | |||
Recursion can create loops! | |||
Here's an infinite loop: | |||
function infinite_loop() | |||
print("Hello there!") | |||
return infinite_loop() | |||
end | |||
infinite_loop() | |||
- | 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) | |||
Here's a loop that asks a user to pick a valid choice: | |||
function get_choice(choices) | |||
local line = io.read() | |||
choice = choices[line] | |||
function | if choice then | ||
return choice | |||
print(" | else | ||
print("Invalid choice! Try again") | |||
return get_choice(choices) | |||
end | |||
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) | |||
== | |||
==State machines== | ==State machines== | ||
Mutual recursion can be used to make state machines! | |||
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() | |||
==Mainstream support== | ==Mainstream support== |
Revision as of 04:14, 3 February 2022
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.
Loops
Recursion can create loops!
Here's an infinite loop:
function infinite_loop() print("Hello there!") return infinite_loop() end infinite_loop()
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)
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)
State machines
Mutual recursion can be used to make state machines!
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()
Mainstream support
- functional programming languages
- lua
- clang mustcall
- webassembly