Recursion and Structural Induction

8.8: Recursive definitions

A recursive definition of a function where the output value of a function is based on the outputs of smaller inputs
Recrusion is the process of computing the value of a function using the result of the function on smaller input values
Recursively defined sets are sets which are specified using the following components:
- Basis: Explicitly states that one or more elements are in a set
- Recursive rule: Shows how to build more elements in the set using the existing ones
- Exclusion statement: States that an element is in the set only if it is in the basis or can be created using recursive rules
  - Typically follows the format of “an element is in the set only if it is given in the basis or can be constructed by applying the recursive rules to elements in the basis”
  - Usually left out of recursive definitions
Examples
- Binary string:
- Binary trees:

Structural induction: a type of induction used to prove thorems about recursively defined sets
Graphic showing the outline and a proof using structural induction:
Formal examples
- Balanced parantheses set:
- Number of vertices in a perfect binary tree:

Recursive algorithms are algorithms that call themselves
- A call that an algorithm makes to itself is called a recursive call
Examples
- Fibonacci:
- String reversal:

Induction can also be used to prove theorems about recursive algorithms, such as their accuracy
- Proof for string reversal:
- Proof for PowerSet function
  - Function:
  - Proof: