Recursion: Difference between revisions

VisualWikitext

Revision as of 03:06, 3 February 2022

Warning: This article is a work in progress! No refunds if it moves!

TODO: This article is about tail calls

- introduction/overview

- 'magic of recursion'?

- lua

- lambdas, etc

Function calls

Let's look at a hypothetical hello world program:

function main()
  value = 0
  print("Hello world!")
  return value
end

The main function does two things here:

Creates a variable with the value 0
Calls the print function with the value "Hello world!"
Returns with the value of the variable

Calling a function is fairly easy:

You save your work and current location
You set the function's arguments
You jump to the beginning of the function

Returning from a function is just as easy:

You set the return value
You restore the previous work
You jump to the previous location

Function calls

Tail calls

Tail call elimination

What if we

- we've been writing code as there's no stack

- tail call elimination

- NOT an optimization, how many optimizations decide which way you can program?

- hints deeper at function calls vs jumps

- structured programming, goto wars

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

- recursion-based control flow

Mainstream support

- functional programming languages

- lua

- clang mustcall

- webassembly

@@ Line 9: / Line 9: @@
 - lua
-==Recursion==
+- lambdas, etc
-As a quick refresher, recursion is when code calls itself.
-Here's a textbook example:
+== Function calls==
+Let's look at a hypothetical hello world program:
-  function fac(n)
+  function main()
-    if n < 1 then
+    value = 0
-     return 1
+    print("Hello world!")
-    else
+    return value
-     return n * fac(n - 1)
-    end
   end
- print(fac(20))
- -- prints 2432902008176640000
-This code has a function 'fac' that takes a number and:
+The main function does two things here:
-* Returns 1 if the number is less than 1
+*Creates a variable with the value 0
-* Calls fac with the number minus 1
+*Calls the print function with the value "Hello world!"
-* Multiplies the result of fac by the number
+* Returns with the value of the variable
-* Returns the multiplied result
-Unfortunately there's a problem with this. When we call fac we need to save our current number to the 'stack' so we can multiply it with the result of fac. If we recurse too many times we run out of memory on the stack to save our numbers.
+Calling a function is fairly easy:
-Because of this tendency to overflow the stack recursion isn't seen much in mainstream programming.
-==Tail calls==
-What if we didn't need to save anything? We could recurse forever without any stack overflows.
-Let's say we rewrite our factorial code to this:
- function fac(n, acc)
-   if n < 1 then
-     return acc
-   else
-     return fac(n - 1, acc * n)
-   end
- end
- print(fac(20, 1))
- -- prints 2432902008176640000
-This new code has a function 'fac' that takes a number and accumulator:
+* You save your work and current location
+* You set the function's arguments
+* You jump to the beginning of the function
-* Returns the accumulator if the number is less than 1
+Returning from a function is just as easy:
-* Multiplies the accumulator by the number
-* Calls fac with the number minus 1 and new accumulator value
-* Returns result
-Instead of storing numbers on the stack and multiplying them afterwards, we now accumulate them as we go.
+* You set the return value
+* You restore the previous work
+* You jump to the previous location
-TODO: explain tail calls
+==Function calls==
-==Tail call elimination==
+== Tail calls==
-We still have a problem. I didn't mention it earlier, but when we call functions in programming languages we also put a return address on the stack. We don't store any numbers on the stack but we still store a return address every time we call fac. If we recurse too many times we still run out of memory.
+== Tail call elimination ==
 What if we