24.2.1. Inductive Definitions

Let us continue our discussion of inductive definitions. Recall that functions like factorial and insertion sort are natural inductive definitions in terms of smaller sub problems.

Inductive definitions are methods of defining functions based on smaller instances of the same function. A good example is the factorial function, which defines n! (n factorial) in relation to (n-1)!. For instance, 5! = 5 × 4!. Similarly, insertion sort can be explained using a smaller segment of an array that has already been sorted. The ability to break a problem into smaller parts is vital for recursive programming.

Imagine you're stacking boxes. You can't stack a large box without first stacking the smaller boxes inside it. Each smaller set of boxes must be perfectly stacked to ensure the larger box remains stable, just like how a complex function relies on simpler parts.

The attraction of looking at inductive definitions is that, we can very easily come up with recursive programs that implement them in a very obvious way. But, the challenge is in identifying the sub problems, ensuring that they are not overlapped.

Inductive definitions make it straightforward to create recursive functions, as the logic mirrors how the function is defined. However, it becomes challenging when trying to identify distinct subproblems. For effective recursion, overlapping subproblems must be avoided. For example, when calculating the factorial of a number, it is important to remember that each factorial of a smaller number should only be calculated once.

Think of doing a puzzle. If you work on finding 'corners' first, they'll be easier to manage. If you keep mixing and overlapping pieces from different sections of the puzzle, it becomes confusing and you waste more time trying to solve it.

Let us see how this works with the very familiar series that you may know of by Fibonacci numbers. The first two Fibonacci numbers are 0 and 1 and then every successive Fibonacci number is obtained by adding these two.

The Fibonacci sequence is a classic example of an inductive definition, where each number is the sum of the two preceding ones, beginning with 0 and 1. Thus, the sequence progresses as 0, 1, 1, 2, 3, 5, etc. Each number is derived from the definition, reinforcing how functions can build upon their previous instances.

This is like building a staircase. Each step relies on the previous two steps to determine how high the next one will be. You can't build a new step (a new number) without knowing how high the last two are.

Now, the problem with this recursive computation is that we may be computing the same values multiple times, leading to inefficiencies.

When using a simple recursive approach for functions like Fibonacci, the same calculations can be repeated many times, especially for larger inputs. This redundancy expands the computational tree, leading to exponential time complexity, which is inefficient.

Think of a librarian searching for a book title in various library sections. If they keep checking the same section repeatedly without noting what they've already done, they waste time and effort. Instead, if they track where they've already looked, they can find the book much faster.

One way to get around this is to make sure that you never reevaluate a sub problem. So, you build up a table called a memory table to keep track of every value for which you have computed the function before.

Memoization involves storing the results of expensive function calls and reusing them when the same inputs occur again. This drastically reduces the number of computations since the system can skip redundant calculations by simply referencing stored values.

Consider a chef who notes down their secret recipes. If they write down how to prepare a dish, they'll never need to remember the exact steps again. They can always reference the recipe instead of starting from scratch each time.

Now, with memoization, each time we compute a value, we check if it’s already in our memo table before doing any recursive calculations.

When implementing memoization, a check is performed before recursively computing values. If a value has already been computed, it is fetched from the memo table instead of being recalculated. This change leads to more efficient execution, converting exponential time complexity into linear time complexity.

Imagine a student doing homework. If they wrote down the answers to similar questions, next time when they face the same question, they can just refer to their previous notes instead of solving it again. This saves time and effort.

The other term that we introduce is dynamic programming. Dynamic programming tries to eliminate the recursive part of evaluating an inductive definition.

Dynamic programming and memoization both aim to optimize recursive processes. However, while memoization caches function results to avoid duplicate computations, dynamic programming anticipates the necessary values and fills in a table iteratively without recursion. This straightforward approach can also improve performance by avoiding the overhead of function calls.

Think of a carpenter building a series of identical shelves. Instead of cutting each shelf separately (like recursion), they cut all shelves at once in a single go (like dynamic programming). This method saves time and effort.

In summary, we have seen two strategies to make recursive computations of inductive functions more efficient. The first is memoization, which avoids redundant calculations. The second is dynamic programming, which uses iterative evaluation to compute values efficiently.

These strategies illustrate how understanding the structure of a problem can lead to more efficient solutions. By leveraging the properties of inductive definitions, both memoization and dynamic programming can significantly reduce computation times.

Just as a savvy traveler may plan their route in advance, tracing paths and landmarks to avoid unnecessary detours (like dynamic programming), a methodical student may use their notes efficiently to save time when studying for exams (like memoization).

--