23.1. Inductive Definitions

The starting point of dynamic programming is to consider, what we would call inductive definitions. Now, there are many very simple functions which we come across which are inductive.

Inductive definitions are foundational concepts in mathematics and computer science that allow us to define complex functions based on simpler instances of the same function. For instance, a function defined inductively specifies its base case and a rule to compute its value for larger inputs using the same function with smaller inputs.

Think of inductive definitions like baking a cake. You have a basic recipe that tells you how to bake a cake from scratch (the base case), and then you have variations of that recipe that modify certain ingredients (the inductive steps). You build upon your basic cake recipe to create chocolate cake, vanilla cake, etc., much like how an inductive definition builds upon simpler cases.

So, we all know that mathematically n factorial is n times n minus 1 factorial. So, we can write an inductive definition of factorial as follows. The base case is when n is 0 and in this case the factorial is 1, so f of 0 is 1. And in general, if we have n greater than 0, then f of n is given by n times f of n minus 1.

The factorial function, denoted as n!, is defined using basic induction. When n is 0, the factorial is simply defined as 1 (base case). For any positive integer n, the factorial is expressed as n multiplied by the factorial of (n-1). This means that to compute the factorial of n, you must first compute the factorial of all integers less than n until you reach 0.

Imagine you are stacking boxes starting from the ground up. The total number of ways to arrange all the boxes (n!) depends on how you stack the boxes in each layer below it. You start with a single box (0!), and as you add more boxes, each additional box's arrangement depends on how the lower boxes are stacked.

This kind of inductive definition is not restricted only to numeric problems, you can also do it for structural problems. So, for an example in a list or an array, you can consider a sub list or a sub array as a smaller problem.

Inductive definitions can also apply to structural problems like sorting a list or working with arrays. For example, you can define the process of sorting a list by first sorting a smaller part of the list (sub-list) and then combining it with the sorted part. This recursive reasoning allows using simpler components to solve larger problems.

Consider organizing books on a shelf. You might first pick a few books to arrange (the sub-list), once those are in order, you can gradually weave in the rest of the books into the already organized stack. Each time, you focus only on a smaller subset until the entire shelf is organized.

One of the attractions of having inductive definitions is that they yield in a very natural way recursive programs. So, we do not have to think much, we can almost take the inductive definition and directly translate it as a program.

The beauty of inductive definitions lies in their ability to define recursive functions easily. A recursive program can literally mirror the structure of an inductive definition. You define the base case and use recursive calls for larger inputs without needing extensive restructuring of code.

Think of a recursive program like a person using a mirror to check their hair. They can see their reflection and, for every reflection of themselves, they can check a smaller part of their hair until they reach the back of their head. Each reflection helps them understand the bigger picture step by step.

What such inductive definitions exploit is what is sometimes called the optimal substructure property. So, what it means is that you solve the original problem by combining solutions to sub-problems.

Inductive definitions are often connected to the optimal substructure property, which indicates that optimal solutions of a problem can be constructed efficiently from optimal solutions of its sub-problems. In other words, solving a larger problem optimally can depend on solving smaller identical problems first.

Think of building a pyramid with blocks. To ensure stability, each layer must be optimally designed using the arrangements of the blocks on the layer below. The overall structure relies on how well you arrange the smaller layers.

So, here is a very simple way of describing insertion sort. If I want to sort n elements... we look at the rest of the list starting from the second element and we recursively sort it and then we insert the first element into the sorted list.

Insertion sort is a classic example of an inductive definition in action. You start with the first element considered sorted. For each new element, you 'insert' it into the correct position in the already sorted subset of the array. This indicates a direct use of inductive definitions where sorting n elements relies on sorting (n-1) elements first.

Imagine organizing a stack of cards. You begin with one card, then with each new card, you find the right place to insert it into the sorted stack of cards above. The method directly reflects how you would sort progressively larger sets of cards using the same principle!

--