There is still one type of proof we need to cover… but first we’re going to take a little bit of a detour.
It is helpful to understand recursion before we move on to the next kind of proof!
There is still one type of proof we need to cover… but first we’re going to take a little bit of a detour.
It is helpful to understand recursion before we move on to the next kind of proof!
Recursion is the idea of solving a problem by breaking it into smaller problems.
Here is an example of what recursion would look like in a programming language like Python.
Say we want to write a program that returns \(n!\).
Def factorial:
input: natural number n
if n == 1: #base case
return 1
else: #recursive rule
return n * factorial(n-1)
We just gave an example of a function that is defined recursively.
You can also recursively define sets, relations, tuples, lists, sequences, etc…
There are two main parts of any recursive definition:
Base case: Empty list \(\langle ~ \rangle\)
Recursive rule: For any element \(a \in A\) and all lists \(l \in L\), \(cons(a,l)\) is a list in \(L\).