Recursion Flashcards
Find the Greatest Common Divisor of 2 numbers
- Brute force - find the smallest number of both inputs and loop from that to 1 to find if both the numbers are divisible by it. If we find remainder as 0 for both then return.
O(n)
~~~
function gcd(testVariable1, testVariable2) {
const smaller = testVariable1 < testVariable2? testVariable1: testVariable2;
for(let number = smaller; number > 0 ; number–){
if(testVariable2%number ===0 && testVariable1%number ===0){
return number;
}
}
}
~~~
- Euclidean Algorithm - O(log n)
gcd(m,n) is same as gcd(m-n,n)
The naive approach to finding𝐺𝐶𝐷of2numbers is to list all their divisors. Then pick the common divisors, and then select the greatest out of them.
However, an easy mathematical simplification can make our task easier.
The idea behind calculating𝐺𝐶𝐷is: If𝑚>𝑛 𝐺𝐶𝐷(𝑚,𝑛)is the same as𝐺𝐶𝐷(𝑚−𝑛,𝑛)
This is because if𝑚/𝑑and𝑛/𝑑both leave no remainder, then(𝑚−𝑛)/𝑑leaves no remainder, either.
function gcd(testVariable1, testVariable2) {
if(testVariable1 === testVariable2) return testVariable2;
if(testVariable1 > testVariable2){
return gcd(testVariable1-testVariable2, testVariable2)
}else{
return gcd(testVariable1, testVariable2-testVariable1);
}
}
How to find Pascal triangles n row
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1
function pascalTriangleRow(n) {
if (n === 0) {
return [1]; // Base case for the 0th row
} else if (n === 1) {
return [1, 1]; // Base case for the 1st row
}
let previousRow = pascalTriangleRow(n - 1);
let currentRow = [1]; // Every row starts with 1
for (let i = 1; i < previousRow.length; i++) {
currentRow[i] = previousRow[i - 1] + previousRow[i];
}
currentRow.push(1); // Every row ends with 1
return currentRow;
}
// Example usage:
console.log(pascalTriangleRow(5));Convert decimal to binary
- keep dividing the number by 2
function decimalToBinary(testVariable) {
if(testVariable <= 1){
return String(testVariable);
}
return decimalToBinary(Math.floor(testVariable/2)) + decimalToBinary(testVariable%2);
}
Is palindrome using recursion
function isPalindrome(testVariable) {
// Base case
if (testVariable.length <= 1) { // Strings that have length 1 or 0 are palindrome
return true;
}
// Recursive case
else if (testVariable[0] == testVariable[testVariable.length - 1]) { // compare the first and last elements
return isPalindrome(testVariable.substring(1, testVariable.length - 1));
}
return false;
}
// Driver Code
console.log(isPalindrome("madam"));Reverse a stack without using additional stack or array
import Stack from './stack.js'
function reverse(stack) {
if (stack.isEmpty()) {
return;
}
// Step 1: Remove the top element
let temp = stack.pop();
// Step 2: Reverse the remaining stack
reverse(stack);
// Step 3: Insert the element at the bottom
insertAtBottom(stack, temp);
}
function insertAtBottom(stack, element) {
if (stack.isEmpty()) {
stack.push(element);
} else {
// Hold all items in Function Call Stack until we reach end of the stack
let temp = stack.pop();
insertAtBottom(stack, element);
// Once the item is inserted at the bottom, push the held items back
stack.push(temp);
}
}
Write a function that takes in an array of unique integers and returns an array of all permutations of those integers in no particular order.
base case - if start === array.length then add the array items to result
swap start and index elements -> recursively call function with start incremented -> swap back numbers (backtracking)
function getPermutations(nums) {
const result = [];
if(!nums.length) return [];
// Helper function to generate permutations using swapping
function generatePermutations(start) {
// If we have reached the end of the array, add the current permutation to the result
if (start === nums.length) {
result.push([...nums]);
return;
}
// Loop through the array and swap each element with the start element
for (let i = start; i < nums.length; i++) {
// Swap the current element with the start element
[nums[start], nums[i]] = [nums[i], nums[start]];
// Recursively generate permutations for the next position
generatePermutations(start + 1);
// Swap back to restore the original array
[nums[start], nums[i]] = [nums[i], nums[start]];
}
}
// Start the recursion from the first position
generatePermutations(0);
return result;
}
// Do not edit the line below.
exports.getPermutations = getPermutations;
Powerset
Write a function that takes in an array of unique integers and returns its powerset.
The powerset P(X) of a set X is the set of all subsets of X. For example, the powerset of [1,2] is [[], [1], [2], [1,2]].
Note that the sets in the powerset do not need to be in any particular order.
Sample Input
array = [1, 2, 3]
Sample Output
[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
use iterative solution
create result array with empty subset result = [[]]
loop thru all the items and generate new subsets from existing results
function powerset(array) {
const result = [[]];
for (let num of array) {
const len = result.length;
for (let i = 0; i < len; i++) {
result.push([...result[i], num]);
}
}
return result;
}
How to solve recursion problems
To solve recursion problems more easily, follow these steps:
- Understand the Problem: Ensure you fully understand the problem, including all the requirements and constraints.
- Identify the Recursive Case: Determine how the problem breaks down into smaller, similar problems. This is the heart of the recursive solution.
- Base Case: Identify the simplest possible cases which can be solved without further recursion. These prevent infinite recursion.
- Write the Recursive Function: Implement the recursive case and ensure it moves towards the base case.
- Test with Simple Inputs: Start with simple inputs that are easy to compute manually to ensure your function behaves as expected.
- Visualize with a Tree Diagram: If you’re stuck, draw a diagram showing how your function calls itself. This helps in understanding the recursion flow.
- Use Memoization if Necessary: If your recursive function recalculates the same values, use memoization to store previously calculated values and avoid redundant calculations.
Starting with these steps can help in building a more intuitive understanding of recursion and make solving such problems easier.
use recursive leap of failt that the solution will work for smaller values like n-1
https://www.youtube.com/watch?v=ye1kMmRtlw8
https://www.youtube.com/watch?v=ngCos392W4w
find nth fib number
using recursion with memoization O(n) time , O(n) space
// T O(n)
// S O(n)
function getNthFib(n, cache = new Map([
[1,0],
[2,1]
])) {
if (cache.has(n)) {
return cache.get(n)
}
const result = getNthFib(n - 1) + getNthFib(n - 2);
cache.set(n, result);
return result;
}
Iterative
~~~
// T O(n)
// S O(1)
function getNthFib(n) {
const lastTwo = [0, 1];
let counter = 2;
while(counter < n){
const newNumber = lastTwo[0]+lastTwo[1];
lastTwo[0] = lastTwo[1]; lastTwo[1] = newNumber; counter++; }
return n > 1 ? lastTwo[1]: lastTwo[0];
}
~~~
