# Recursion via Mathematical Induction

How to think about recursion questions:

The best way to think about recursion questions is to think in terms of Mathematical Induction.

From Wiki:

```
Mathematical induction is a mathematical proof technique used to prove a given statement about any well-ordered set. Most commonly, it is used to establish statements for the set of all natural numbers.
```

To solve recursion questions more intuitively we should think in terms of MI.

Here is how we prove a particular formula using MI:

**The basis (base case)**: prove that the statement holds for the first natural number n. Usually, n = 0 or n = 1, rarely, n = –1 (although not a natural number, the extension of the natural numbers to –1 is still a well-ordered set).**The inductive step**: prove that, if the statement holds for some natural number n, then the statement holds for n + 1.

The general idea is to write base cases (for n = 0) and then solve for F(n) using F(n-k)s (K <= n).

Let's take an easy example:

Find the height of the tree.

- Base condition:

For a tree without any node, it's height is zero:

```
if root == None:
return 0
```

2. Inductive step:

Using F(n) we can find out the height of F(n+1).

In other words, `F(root) = 1 + max(F(root_of_left_subtree) + F(root_of_right_subtree))`

.

That's it.

```
def height(root):
if root == None:
return 0
return 1 + max(height(root.left), height(root.right))
```

Check if all elements in the array are sorted

- Base condition:

if array contains one or zero elements then it's sorted.

```
if index <= 1:
return True
```

- Inductive step

F(n + 1) is sorted if:

- arr[n] < arr[n + 1]
- F(n) is sorted

```
return arr[n] < arr[n + 1] and F(n)
```

That's it

```
def sorted(index, arr):
if index <= 1:
return True
return sorted(index - 1, arr) and arr[index] > arr[index - 1]
```