24.2.3. Catch and Efficiency of Recursive Function

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

In this section, we begin by recalling the concept of inductive definitions as they relate to recursive functions. An inductive definition allows us to define complex functions based on simpler, smaller problems. For example, calculating the factorial of a number can be broken down into recursive calls that solve for smaller numbers until a base case is reached.

Imagine building a Lego structure. You start by constructing a base layer, then progressively add more layers on top, each one built from the previous layer. Similarly, recursive functions build solutions by layering smaller, simpler solutions until the entire structure is complete.

But, the challenges is, in identifying the sub problems, I am making sure that they are not overlapped.

The key challenge with recursive functions arises when identifying the subproblems involved. These subproblems should not overlap, meaning that each call must be unique and independent. If they overlap, the same computation might be repeated multiple times, leading to inefficiency in the overall process.

Think of baking a cake where each tier is dimensionally distinct and doesn't affect the others. If, instead, you tried to bake multiple cakes in a mixed-up fashion, you'd end up repeating tasks or using the wrong ingredients for each layer. This mismanagement results in inefficiency, just like overlapping subproblems in recursion.

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

The Fibonacci numbers are defined recursively: the first two numbers in the sequence are 0 and 1, and each subsequent number is the sum of the two preceding ones. This sequence serves as an excellent example of how a recursive function can be derived from simpler cases: Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2). This formulation highlights the inductive nature of the series.

Consider a family tree where each generation branches out into more family members. The first generation may consist of two parents, who then lead to multiple children in the next generation. Similarly, each Fibonacci number is built upon the 'parents' of its two previous entries, creating a branching, self-referential pattern.

So, where is the catch? So, let us see how this would work on a small input like we have just saw Fibonacci. ... So, the problem we can see is that functions that Fibonacci of 3 have been computed twice in full and full complexity...

The catch with using recursion for the Fibonacci sequence is that it leads to redundant calculations. For example, computing Fibonacci(5) would require computing Fibonacci(4) and Fibonacci(3). The process continues recursively down the tree, leading to the fact that Fibonacci(3) is computed multiple times. This redundancy results in an exponential time complexity due to the repeated evaluations of the same subproblems.

Think of a detective solving a case by repeatedly questioning the same witness, not realizing they already have the answers from previous interviews. This waste of time and resources mirrors what happens in recursive calculations when subproblems get revisited unnecessarily.

So, one way to get around this is to make sure that you never reevaluate a sub problem. So, you build up a table which is sometimes called a memory table...

Memoization addresses the inefficiencies of recursion by storing results of previously computed values in a 'memory table'. Before computing the value of a function, the program checks if the value has already been computed and stored. If it has, it retrieves the result from the table, which prevents redundant calculations and thus improves efficiency.

This is like taking notes in a meeting. Instead of trying to remember every detail during future discussions, you jot down key points. When revisiting the topic, you can quickly look back at your notes for the information, rather than trying to recall it from memory.

So, how does memoization work? ... So, that you can look at up and see we already computed it. So, it is called memoization.

Memoization involves creating a data structure to store previously calculated values (like the Fibonacci results). Each time a function is called, it first checks if the value is already in the table. If not, the function computes the value, stores it, and then returns it. This dramatically reduces the number of calculations by ensuring that each unique computation is only done once.

Imagine a librarian who organizes books alphabetically. Instead of searching through the entire library every time someone asks for a specific book, the librarian can quickly check the catalog, making the process significantly faster and more efficient.

So, the other term that we introduce in the last lecture is dynamic programming. So, what dynamic programming does is it tries to eliminate the recursive part of evaluating an inductive definition...

Dynamic programming differs from memoization in that it not only stores previously computed values but also anticipates which values will be needed ahead of time. It constructs a solution iteratively rather than recursively. By synthesizing the dependency relationships between subproblems, it can fill in values in an organized manner much more efficiently than recursive calls can manage.

Think of a waiter in a restaurant who prepares a sequence of orders in a batch rather than one at a time. By laying out all the orders, the waiter can gather ingredients for all together, streamlining the process rather than going back and forth for each individual dish.

--