javascript
examples
examples.js⚡javascript
/**
* =====================================================
* 5.8 RECURSION - EXAMPLES
* =====================================================
* Functions that call themselves
*/
// =====================================================
// 1. BASIC RECURSION - COUNTDOWN
// =====================================================
console.log('--- Basic Recursion: Countdown ---');
function countdown(n) {
// Base case
if (n <= 0) {
console.log('Done!');
return;
}
// Recursive case
console.log(n);
countdown(n - 1);
}
countdown(5);
// =====================================================
// 2. FACTORIAL
// =====================================================
console.log('\n--- Factorial ---');
function factorial(n) {
// Base case
if (n <= 1) return 1;
// Recursive case: n! = n * (n-1)!
return n * factorial(n - 1);
}
console.log('5! =', factorial(5)); // 120
console.log('0! =', factorial(0)); // 1
console.log('10! =', factorial(10)); // 3628800
// =====================================================
// 3. FIBONACCI
// =====================================================
console.log('\n--- Fibonacci ---');
// Basic (inefficient for large n)
function fibonacci(n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log('First 10 Fibonacci numbers:');
for (let i = 0; i < 10; i++) {
process.stdout.write(fibonacci(i) + ' ');
}
console.log();
// Memoized (efficient)
function fibMemo(n, memo = {}) {
if (n in memo) return memo[n];
if (n <= 1) return n;
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
console.log('fib(50) =', fibMemo(50));
// =====================================================
// 4. POWER / EXPONENTIATION
// =====================================================
console.log('\n--- Power ---');
function power(base, exponent) {
if (exponent === 0) return 1;
if (exponent < 0) return 1 / power(base, -exponent);
return base * power(base, exponent - 1);
}
console.log('2^8 =', power(2, 8)); // 256
console.log('3^4 =', power(3, 4)); // 81
console.log('2^-3 =', power(2, -3)); // 0.125
// =====================================================
// 5. SUM OF ARRAY
// =====================================================
console.log('\n--- Sum of Array ---');
function sum(arr) {
// Base case: empty array
if (arr.length === 0) return 0;
// Recursive case: first + sum of rest
return arr[0] + sum(arr.slice(1));
}
console.log('sum([1,2,3,4,5]) =', sum([1, 2, 3, 4, 5])); // 15
// With index (more efficient)
function sumWithIndex(arr, index = 0) {
if (index >= arr.length) return 0;
return arr[index] + sumWithIndex(arr, index + 1);
}
console.log('sumWithIndex([1,2,3,4,5]) =', sumWithIndex([1, 2, 3, 4, 5]));
// =====================================================
// 6. STRING OPERATIONS
// =====================================================
console.log('\n--- String Operations ---');
// Reverse string
function reverse(str) {
if (str.length <= 1) return str;
return reverse(str.slice(1)) + str[0];
}
console.log("reverse('hello') =", reverse('hello'));
// Check palindrome
function isPalindrome(str) {
str = str.toLowerCase().replace(/[^a-z]/g, '');
if (str.length <= 1) return true;
if (str[0] !== str[str.length - 1]) return false;
return isPalindrome(str.slice(1, -1));
}
console.log("isPalindrome('racecar') =", isPalindrome('racecar'));
console.log("isPalindrome('hello') =", isPalindrome('hello'));
console.log(
"isPalindrome('A man a plan a canal Panama') =",
isPalindrome('A man a plan a canal Panama')
);
// =====================================================
// 7. ARRAY OPERATIONS
// =====================================================
console.log('\n--- Array Operations ---');
// Find element
function includes(arr, target, index = 0) {
if (index >= arr.length) return false;
if (arr[index] === target) return true;
return includes(arr, target, index + 1);
}
console.log('includes([1,2,3,4], 3) =', includes([1, 2, 3, 4], 3));
console.log('includes([1,2,3,4], 5) =', includes([1, 2, 3, 4], 5));
// Find max
function findMax(arr, index = 0, max = -Infinity) {
if (index >= arr.length) return max;
return findMax(arr, index + 1, arr[index] > max ? arr[index] : max);
}
console.log('findMax([3,1,4,1,5,9,2,6]) =', findMax([3, 1, 4, 1, 5, 9, 2, 6]));
// Count occurrences
function countOccurrences(arr, target, index = 0) {
if (index >= arr.length) return 0;
const count = arr[index] === target ? 1 : 0;
return count + countOccurrences(arr, target, index + 1);
}
console.log(
'countOccurrences([1,2,1,3,1], 1) =',
countOccurrences([1, 2, 1, 3, 1], 1)
);
// =====================================================
// 8. FLATTEN NESTED ARRAY
// =====================================================
console.log('\n--- Flatten Array ---');
function flatten(arr) {
let result = [];
for (const item of arr) {
if (Array.isArray(item)) {
result = result.concat(flatten(item));
} else {
result.push(item);
}
}
return result;
}
console.log('flatten([1,[2,[3,[4]]]]) =', flatten([1, [2, [3, [4]]]]));
console.log(
'flatten([[1,2],[3,[4,5]]]) =',
flatten([
[1, 2],
[3, [4, 5]],
])
);
// With depth limit
function flattenDepth(arr, depth = 1) {
if (depth < 1) return arr.slice();
return arr.reduce((acc, item) => {
if (Array.isArray(item)) {
return acc.concat(flattenDepth(item, depth - 1));
}
return acc.concat(item);
}, []);
}
console.log('flattenDepth([1,[2,[3]]], 1) =', flattenDepth([1, [2, [3]]], 1));
// =====================================================
// 9. DEEP CLONE OBJECT
// =====================================================
console.log('\n--- Deep Clone ---');
function deepClone(obj) {
// Handle primitives and null
if (obj === null || typeof obj !== 'object') {
return obj;
}
// Handle Date
if (obj instanceof Date) {
return new Date(obj.getTime());
}
// Handle Array
if (Array.isArray(obj)) {
return obj.map((item) => deepClone(item));
}
// Handle Object
const clone = {};
for (const key in obj) {
if (obj.hasOwnProperty(key)) {
clone[key] = deepClone(obj[key]);
}
}
return clone;
}
const original = {
a: 1,
b: { c: 2, d: [3, 4] },
e: new Date(),
};
const cloned = deepClone(original);
console.log('Original:', original);
console.log('Cloned:', cloned);
console.log('Are they equal?', original === cloned); // false
console.log('Are nested equal?', original.b === cloned.b); // false
// =====================================================
// 10. TRAVERSE NESTED OBJECT
// =====================================================
console.log('\n--- Traverse Object ---');
function getAllValues(obj) {
let values = [];
for (const key in obj) {
if (typeof obj[key] === 'object' && obj[key] !== null) {
values = values.concat(getAllValues(obj[key]));
} else {
values.push(obj[key]);
}
}
return values;
}
const nested = {
a: 1,
b: {
c: 2,
d: {
e: 3,
f: 4,
},
},
g: 5,
};
console.log('All values:', getAllValues(nested));
// Find nested value by key
function findValue(obj, targetKey) {
if (obj.hasOwnProperty(targetKey)) {
return obj[targetKey];
}
for (const key in obj) {
if (typeof obj[key] === 'object' && obj[key] !== null) {
const result = findValue(obj[key], targetKey);
if (result !== undefined) return result;
}
}
return undefined;
}
console.log("Find 'e':", findValue(nested, 'e')); // 3
// =====================================================
// 11. TAIL RECURSION
// =====================================================
console.log('\n--- Tail Recursion ---');
// Regular recursion (not tail)
function factorialRegular(n) {
if (n <= 1) return 1;
return n * factorialRegular(n - 1); // Multiplication after call
}
// Tail recursive with accumulator
function factorialTail(n, acc = 1) {
if (n <= 1) return acc;
return factorialTail(n - 1, n * acc); // Nothing after call
}
console.log('factorialTail(5) =', factorialTail(5));
// Tail recursive fibonacci
function fibTail(n, a = 0, b = 1) {
if (n === 0) return a;
if (n === 1) return b;
return fibTail(n - 1, b, a + b);
}
console.log('fibTail(10) =', fibTail(10));
console.log('fibTail(50) =', fibTail(50));
// =====================================================
// 12. BINARY SEARCH
// =====================================================
console.log('\n--- Binary Search ---');
function binarySearch(arr, target, left = 0, right = arr.length - 1) {
if (left > right) return -1;
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] > target) return binarySearch(arr, target, left, mid - 1);
return binarySearch(arr, target, mid + 1, right);
}
const sorted = [1, 3, 5, 7, 9, 11, 13, 15];
console.log('Find 7:', binarySearch(sorted, 7)); // 3
console.log('Find 6:', binarySearch(sorted, 6)); // -1
// =====================================================
// 13. GENERATE PERMUTATIONS
// =====================================================
console.log('\n--- Permutations ---');
function permutations(arr) {
if (arr.length <= 1) return [arr];
const result = [];
for (let i = 0; i < arr.length; i++) {
const current = arr[i];
const remaining = [...arr.slice(0, i), ...arr.slice(i + 1)];
const perms = permutations(remaining);
for (const perm of perms) {
result.push([current, ...perm]);
}
}
return result;
}
console.log('permutations([1,2,3]):');
console.log(permutations([1, 2, 3]));
// =====================================================
// 14. DIRECTORY-LIKE STRUCTURE
// =====================================================
console.log('\n--- Tree Structure ---');
const fileSystem = {
name: 'root',
type: 'folder',
children: [
{ name: 'file1.txt', type: 'file' },
{
name: 'folder1',
type: 'folder',
children: [
{ name: 'file2.txt', type: 'file' },
{ name: 'file3.txt', type: 'file' },
],
},
{
name: 'folder2',
type: 'folder',
children: [
{
name: 'subfolder',
type: 'folder',
children: [{ name: 'file4.txt', type: 'file' }],
},
],
},
],
};
function listFiles(node, indent = '') {
console.log(indent + (node.type === 'folder' ? '📁 ' : '📄 ') + node.name);
if (node.children) {
for (const child of node.children) {
listFiles(child, indent + ' ');
}
}
}
listFiles(fileSystem);
// Count files
function countFiles(node) {
if (node.type === 'file') return 1;
let count = 0;
if (node.children) {
for (const child of node.children) {
count += countFiles(child);
}
}
return count;
}
console.log('\nTotal files:', countFiles(fileSystem));
// =====================================================
// 15. GCD AND LCM
// =====================================================
console.log('\n--- GCD and LCM ---');
// Greatest Common Divisor (Euclidean algorithm)
function gcd(a, b) {
if (b === 0) return a;
return gcd(b, a % b);
}
console.log('gcd(48, 18) =', gcd(48, 18)); // 6
console.log('gcd(100, 25) =', gcd(100, 25)); // 25
// Least Common Multiple
function lcm(a, b) {
return (a * b) / gcd(a, b);
}
console.log('lcm(4, 6) =', lcm(4, 6)); // 12
// =====================================================
// SUMMARY
// =====================================================
console.log('\n--- Summary ---');
console.log(`
RECURSION ESSENTIALS:
• Base case - When to stop
• Recursive case - Call with smaller problem
• Progress toward base case
COMMON PATTERNS:
• Factorial: n! = n × (n-1)!
• Fibonacci: fib(n) = fib(n-1) + fib(n-2)
• Array: process first + recurse on rest
• Tree: process node + recurse on children
OPTIMIZATION:
• Memoization for overlapping subproblems
• Tail recursion with accumulators
• Iterative solution for large inputs
`);