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:

1. 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).
2. 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.

1. 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

1. Base condition:

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

if index <= 1:  
  return True

1. 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]