Recursion: Difference between revisions

From JookWiki
(Add function calls)
(Fix ordering in function calls)
Line 33: Line 33:
Returning from a function is just as easy:
Returning from a function is just as easy:


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



Revision as of 03:07, 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 restore the previous work
  • You set the return value
  • 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