<aside> 💡 Identification

Any problem that requires a Choice → Desision pattern repeatedly is a recursion problem

</aside>

Introduction to Recursion

Identify Recursion

To Identify recursion, you have to recognose if you can identify a Decision Space. If you can identify a decision space, it is a recursion problem

Make Input smaller, but Why?

We do not make input smaller in Recursion. We take a decision and a by product the input size gets smaller

Decision making is Primary.

How to design a Recursive Tree

If you can design a recursive tree, it is a recursion problem

For Example:

Give all the subsets that can be formed by the string “abc”

We have three choices. a , b , c

We can have mave multiple decisions from these choices.

With each Decision, the Input size decreases for the next recursive call.

Suppose we select ‘a’ for the current set, then only b , c remains for the next step.

Lets draw a recursive tree to show this.

Ways to approach a Recursion Problem

After identifying a recursion problem, we can go either of the following two ways

1. Input / Output Choice Diagram
2. Base Case → Hypothesis → Induction

Try to create a Hypothesis. If you fail, try to draw a diagram containing the input and output at different levels

Example:

Write a Function to print 1 to N using Recursion

1. Hypothesis: function printTill(n-1) that has our answer.
2. Base Case: What is the answer for function printTill(1)
3. Induction: After getting the answer for function printTill(n-1) what shall we do?

function printTill(n) {

	if(n==1) console.log(n) // Base Condition 
	
	printTill(n-1) // Hypothesis
	
	console.log(n) // Induction
	
}

Sample Question: Sort an Array using Recursion

Approach:

We would try to approach this problem with the Base Case → Hypothesis → Induction method

Base case:

Q: What is the smallest valid input of this problem?

A: An empty input array

Q: What is the output for this input?

A: Empty Array

Hypothesis:

Q: Suppose our function sortArray(nums) returned a sorted array, and you had to insert another number in this sorted Array, what would you do?

A: We would have to perform the following steps:

1. store the last number in a temp variable
2. Recursively call sortArray(nums) on the subarray exclusing the last number
3. pass this temp and sortArray(nums) into an insert(num, arr) function that inserts a number in a sorted array

Induction

Q. We saw that insert() function in the last step. We need to design that function

A: design an insert function that takes in two arguments,

1. A sorted array
2. A number to insert

var sortArray = function(nums) {
    if(!nums.length) return []
};

var sortArray = function(nums) {
    if(!nums.length) return []

   let temp = nums[nums.length-1]

   return insert(temp, sortArray(nums.slice(0, nums.length-1)))

};

function insert(num, arr) {
    if(!arr || !arr.length) return [num]

    for(let i=0; i<arr.length; i++) {
        if(arr[i]>=num){
            return [...arr.slice(0, i), num, ...arr.slice(i)]
        }
    }
}