May 2022 – bor0's reflective blog

Recursion is one of the things that makes computation happen – whether you’re doing something on your computer, smart TV, or smartphone.

For example, here’s a definition of the addition function represented in first-order logic:

$\forall y, add(0, y, y) \\ \forall x, y, z, add(x, y, z) \to add(S(x), y, S(z))$

Or, the more commonly known variant:

$\begin{aligned} 0+y &= y \\ S(x)+y &= S(x+y) \end{aligned}$

In this blog post, we will generalize recursive functions.

Month: May 2022