2. Recursion and PMI #

Created Saturday 28 December 2019

• Recursion is a easy and intuitive way to solve problems, whose iterative solution may be tedious, and may require a “programmers stack”.
• It’s a **pain **to think of recursion as a stack of activation records, and it’s too slow.
• We **won’t **go into the **tracking detail **of the recursion(before writing the code).
• We will work on recursion using PMI(Principal of Mathematical Induction):

Problem: Prove that P(x) is true for all x ∈ N. Step 1: **Base Case **- F(x) is true for x = anchor point. Mostly F(0) or F(1) is shown to be true. [ Done by observation ] Step 2: Induction Hypothesis - Assume that F(k) is true for some k in the input range. [ This is your hypothesis, it cannot be challenged until the completion of the next step ] Step 3: **Induction Step **- Prove that F(k+1) is true. [ Just check that this is is sync with the hypothesis value, by assuming F(k) is true ] If Step 3 holds then F(k) is true for all n.

**Reason why it works: **1. We have a base. For a unit part of the ladder, we prove that the next unit is there. This is true for all units, since we used a variable ‘k’. Definitely it is true for the base case. Hence the ladder can be progressed for any k in N.

• For any recursion problem, just solve the equivalent PMI of the problem and implement the code.
• Only after that do we make a tree. It is confusing to draw the tree before writing the code, atleast for beginners.

Example: Using PMI for factorial.

int factorial(int n) // exploded view of the code
{
	if(n==0)
		return 1; 	// Base case
	else
	{
		int smallOutput = factorial(n-1); 	// Induction hypothesis: which is the function itself.
		int output = n * factorial(n-1); 	// this is where we put our hypothesis(i.e assumed solution).
		return output;
	}
}
// A simple version(equivalent to the above)
int factorial(int n)
{
	if(n==0)
		return 1; 	// Base case
	return n * f(n-1); // all temp variable are handled by the compiler
}

• We can optimize step 2 and 3 in code. But it is always better to write them seperately when learning recursion. Then mix them acc to the rules of programming.
• Order of the recursive call does matter, it can be a head recursion or a tail recursion.

Flow of a recursive function #

There are 3 things in a recursive functions, in this order

1. Anchor condition
2. Recursive call(s)
3. Small calculation before return, if any.

Note

• Why this order - 2 and 3 are irrelevant for the simple case, and so 1 must appear before them.
• Code may not follow this order, but execution wise it must follow the order.

Recursion rocks #

Recursion is a popular approach for solving problems because recursive solutions are generally easier to think than their iterative counterparts and the code is also shorter and easier to understand.

Using recursion #

In a nutshell:

1. Solve the problem using PMI(for the nth case, not extremes).
2. Write the code.
3. Dry run it using trees.
4. Done !!

Intro to Recursion Notes