### Recursion-Inductive Definitions

Many Mathematic functions are naturally defined inductively

##### Factorial

- 0! = 1
n! = n x (n-1)!

def factiorial(n): if(n==0): return(1) else: return (n*factorial(n-1))

##### Multiplication

- m x 1 = m
m x (n+1) = m + (m x n)

def multiply (m,n): if(n==1): return(m) else: return (m + multiply (m,n-1))

##### Recursion works by

- Define one or more base case
- Inductive step defines f(n) in terms of smaller arguements

### Inductive definition for Lists

Lists can be decomposed as - First (or last) element - Remaining list with one less element

##### How to define list inductively?

- Base Case: Empty list or list of size 1
- Inductive step: f(l) in terms of smaller sublists of l

If you are stuck at any point or have any doubts, drop a message here