Recursion

Introduction

Want to get done the basics for some of this.

Why

Breaks down large chunks into smaller chunks.

When

You use it when problems contain smaller instances of the same problem. E.g. finding how many combinations there are of n items.

Aspects of Recursion

They all have a

• base case
• recursive case

Base Case

This is where the smallest instance of the case can be solved easily. E.g. For number of combinations when the array is empty.

Recursive Case

This is an instance of the problem that shrink the size of the input toward the base case.

Examples

Example Factorial

<syntaxhightlight lang="js"> const factorial = (n) => {

   if(n === 1) return 1
   return n * factorial(n-1)

} </syntaxhightlight>

Example Palindrome

const palindrome = (str) => {
    console.log("calling with",str)
    if(str.length === 0) return true
    if(str.length === 1) return true
    if(str[0] !== str[str.length-1]) return false
    
    return palindrome(str.substr(1, str.length-2))

}

Example Sum

This was a bit of enlightenment for improving speed. Did the sum as you would normally do and you can see on line 3 we slice which means we copy.

const _sum = (numbers, idx) =>  {
    if(numbers.length == 0) return 0
    return n + sum(numbers.slice(1))
}

A better approach is to create a sub function which takes an index and therefore no more slices

const sum = (numbers) => {
    return _sum(numbers, 0)
}

const _sum = (numbers, idx) =>  {
    if(idx == numbers.length) return 0
    return numbers[idx] + _sum(numbers, idx + 1)
}

Example String Reversal

This is where I struggle with recursive. Separating the a) reduce the argument and b) forming the result. It seems very odd to me. Maybe my dyslexic brain is fried

const string_rev = (str) => {
    if(str.length === 0 || str.length === 1) return str

    const result = string_rev(str.slice(1))
    return  result + str[0]
}

console.log("Reverse:", string_rev("FRED"))

So this is really

string_rev("RED") + "F"
 string_rev("ED") + "R"
  string_rev("D") + "E"
   string_rev("") + "D"

More Fib

With Fib we use two calls to the same function. This is known as multi branch recursion.

const fib = (n) => {
    if(n < 0) return 0
    if(n <= 1) return 1
    if(n === 2) return 1

    return fib(n-1) + fib(n-2) 
}

This could be shown as a tree

Climbing Stairs (Recursion)

You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Still trying to connect pictures with questions. So here goes for climb stairs. First a picture for climb stairs where there are 4 stairs. The successful paths (leaf nodes) in green

In the yellow square, the two child nodes, the left +1 step away, and the right +2 steps away. When you see a binary tree, and the children are k+1 and k+2 then you can use Fibonacci f(n) = f(n-1) + f(n-2) to calculate the number of leaf nodes

Combinations

Common questions are

• Given N things, in how many ways can we arrange them
• In how many ways can we do X
• What is the shortest way to do Y

What is a combination

It is a collection of things where the order does not matter. Important is give [a,b] in a combination it is the same as [b,a]. Given a set of n things, there are 2^n possible combinations.

Example

Looking at [a,b,c] this gives the following

To at each level, the left is if you don't take the level value. So at level a on the left branch we take the parent ([]), on the right we take the level value (a).