Grokking-Algorithms

Recursion | 3

In this chapter

Recursion is coding technique used in many algorithms.
Learn how to break problem down into a base case and a recursive case. divide-and-conquer strategy.

There is no performance benefit using Recursion, in fact loops are sometimes better for performance.

quote by Leigh Caldwell on Stack Overflow:

“Loops may achieve a performance gain for your program. Recursion may achieve a performance gain for your programmer"

Base case and recursive case

a recursive function call itsself, its easy to write function incorrectly that ends up in an infinite loop.

Print simple count down using recursive

function countdown(i) {
	console.log("i", i);
	if (i < 1) { // base case

		return;
	}

	countdown(i - 1);
}

countdown(10);

The stack

When you insert an item its get added to a top of a list, when you read an item, you only read the topmost item.

its like Last in First Out (LIFO)

push (insert) and pop (remove) from end

this data sructure called Stack.

The call stack

computer uses a stack internally called callstack

e.g

function greet(name) {
	console.log(`Hello ${name}`);

	greet2(name);
	console.log("getting ready to say bye...");
	bye();
}

function greet2(name) {
	console.log(`How are you ${name} ? `);
}

function bye() {
	console.log(`ok bye!`);
}

Suppose you call greet("maggie") first computer allocate box of memory for that fuction call

 |---------------|
 |_______________|
 |	         |
 |_______________|

  ↑ this memory box :)

lets use memory, the variable name set to maggie needs to save in a memory

 |_______________|
 |	 GREET   |
 |_______________|
 |name: | MAGGIE |
 |_______________|

Every time make a fuction call, saves the value for all the variables for that call in memory like this next you print hello, maggie! then you call greet2("“maggie")


 |_______________|
 |	 GREET 2 |
 |_______________|
 |name: | MAGGIE |
 |_______________|
 |_______________|
 |	 GREET   |
 |_______________|
 |name: | MAGGIE |
 |_______________|

computer is using stack for these boxes, second box is added on top of first one. You print how are you, maggie? then return from fuction call the box on top of the stack gets popped off.

 |_______________|
 |	 GREET   |
 |_______________|
 |name: | MAGGIE |
 |_______________|

now the topmost box on the stack is for greet function which means tou returned back to greet function when you call greet2 function , the greet function was partially completed main idea When you call a function from another function, the calling function is paused in a partially completed state all the values of the variables for that fuction are still store in memory Now greet2 function is completed, you’re back to the greet function, and you pick up where you left off. First you print getting ready to say bye…. You call the bye function.
box added to the top of the stack then print ok bye!

 |_______________|
 |	 GREET   |
 |_______________|
 |name: | MAGGIE |
 |_______________|

now control bacl to the greet function. There’s nothing else to be done, so you return from the greet function too. This stack, used to save the variables for multiple functions, is called the call stack.

The call stack with recursion

Recursive functions use the call stack

e.g

function. factorial(5) is written as 5!, and it’s
defined like this: 5! = 5 * 4 * 3 * 2 * 1.

function fact(x) {
	if (x == 1) return 1;
	else return x * fact(x - 1);
}

Call Stack

Summary of the Call Stack

fact(3) // 1st call
	└ fact(2)  //  2nd call
	└ fact(1)  // 3rd call



- Base case reached; returns 1.
Stack then resolves upward: fact(2) returns 2, fact(3) returns 6.

NOTE: Using stack is convenient, but come with cost saving all info can take up lot of memory

each of those function takes up some memory and when stack is to tall, that means your computer is saving information of many function calls at the point two options

You can rewrite using loop
You can use tail recursion

Practical examples on recursion

function toLowerCamelCase(str, i = 0, toCapital = false) {
	if (i >= str.length) return "";

	let char = str[i];

	if (char == "_") {
		// add if need extra  char === '_' || char === ' '
		return toLowerCamelCase(str, i + 1, true);
	}
	let nextChar = toCapital ? char.toUpperCase() : char.toLowerCase();

	return nextChar + toLowerCamelCase(str, i + 1, false);
}

console.log("", toLowerCamelCase("user_name")); // userName

function reverse(str, result = "") {
	if (str == "") return result;

	return reverse(str.substring(1), str[0] + result);
}

console.log("reverse", reverse("hello")); // olleh

function isPalindrom(str) {
	if (str.length < 2) return true;
	else if (str[0] != str[str.length - 1]) return false;
	else {
		return isPalindrom(str.slice(1, -1)); // remove first & last char
	}
}
console.log("", isPalindrom("rotator"));
console.log("", isPalindrom("hello"));

Quicksort | 4

In this chapter

Divide-and-conquer
quicksort, an elegant sorting algorithm that’s often used in practice

how D&C works:

Figure out a simple case as the base case.
Figure out how to reduce your problem and get to the base case.

Quicksort

Quicksort is a sorting algorithm.
Quicksort also uses D&C

Let’s use quicksort to sort an array. simplest array that a sorting algorithm can handle

No need to sort

[]
[20]

empty array or array with just one element will be a base case

function quicksort(array) {
	if (array.length < 2) return array;
}

lets look bigger array with two elements 1 & 7

| 1 | 7 |

check if first element is smaller than the
second if isn't swap them.

what about three elements | 33 | 15 | 10 |

We using D&C so we want to array break down until get base case

Here’s how quicksort works. First, pick an element from the array. This element is called the pivot.

lets pick first item in the array is the pivot

now find elements smaller than the pivot and the elements larger than the pivot.

 | 15 | 10 |  33   [ ]

33 is Pivote

number greater than 33 is empty

This is called partitioning

A sub-array of all the numbers less than the pivot
The pivot
A sub-array of all the numbers greater than the pivot

if sub array is sorted the you combined whole thing like

left array + pivote + right array & you wil get sorted array

| 10 | 15 | 33 |

How will you sort subarray

the quicksort base case already knows how to sort arrays of two elements (the left sub-array) and empty arrays (the right sub-array).

call quicksort on the two sub-arrays and then combine the results, you get a sorted array!

quicksort([15, 10]) + [33] + quicksort([])
-> [10, 15, 33]    <-- A sorted array

This will work with any pivot. Suppose you choose 15 as the pivot instead.

| 10 | 15 |   [33]

both sub array only one element , u know how to sort those.

Here are the steps

Pick a pivot.
Partition the array into two sub-arrays: elements less than the pivot and elements greater than the pivot.
Call quicksort recursively on the two sub-arrays

function quicksort(nums) {
	if (nums.length < 2) return nums;

	let pivot = nums[0];

	let smaller = nums.filter((n) => n < pivot);
	let equal = nums.filter((n) => n === pivot);
	let greater = nums.filter((n) => n > pivot);

	return quicksort(smaller).concat(equal).concat(quicksort(greater));
}

console.log(quicksort([10, 5, 2, 2, 3]));

Merge sort vs. quicksort

Quicksort versus merge sort is one example. Quicksort has a smaller constant than merge sort. So if they’re both O(n log n) time, quicksort is faster. And quicksort is faster in practice because it hits the average case way more often than the worst case.

sunil-bagde/Grokking-Algorithms-Chap-3-4.md