Recursion is a programming concept where a function calls itself in order to solve a problem. A recursive function typically has a base case that stops the recursion and one or more recursive cases that call the function itself.
Behind the scenes, each recursive call adds a stack frame including the function arguments, local variables etc. As calls return, stack frames are popped off. Recursion utilizes the call stack and stack frames to keep track of function calls. Proper base conditions are needed to unwind the stack properly.
Recursion is helpful for solving problems that can be naturally broken down into smaller sub-problems of the same type. It can be a powerful tool for tasks like:
A stack overflow error occurs when a recursive function calls itself too many times and exceeds the memory allocated for the call stack. To avoid this error, you need to ensure that your recursive function has a base case that stops the recursion when a certain condition is met. You also need to make sure that your recursive case reduces the problem size and moves closer to the base case. Otherwise, you may end up with infinite recursion that never reaches the base case.
Another way to avoid stack overflow errors is to use an iterative approach instead of a recursive one. This means using a loop and a data structure (such as a stack or a queue) to store the intermediate results, rather than relying on the call stack. This can improve the performance and memory efficiency of your algorithm, but it may also make the code more complex and less readable.
Tail call optimization (TCO) is a feature that allows a tail call to reuse the current stack frame, instead of creating a new one. This can improve the performance and memory efficiency of recursive functions, and avoid stack overflow errors. However, not all JavaScript engines support TCO, and it only works in strict mode.
Factorial of a number is a mathematical function that is denoted by an exclamation mark (!). It is defined as the product of all positive integers less than or equal to the given number. For example, the factorial of 5 is 5 x 4 x 3 x 2 x 1 = 120, written as 5! = 120.
function factorial(n) {
// base case: n is zero
if (n === 0) {
return 1;
}
// recursive case: n is positive
else {
return n * factorial(n - 1);
}
}
console.log(factorial(5)); // 120Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones. For example, the Fibonacci sequence starts with 1, 1, 2, 3, 5, 8, 13, etc.
function fibonacci(n) {
// base case: n is 1 or 2
if (n === 1 || n === 2) {
return 1;
}
// recursive case: n is greater than 2
else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}A palindrome is a word or phrase that is the same forward and backward. For example, “racecar” and “madam” are palindromes.
function isPalindrome(str) {
// base case: str is empty or has one character
if (str.length <= 1) {
return true;
}
// recursive case: check if the first and last characters are the same
else {
let first = str[0];
let last = str[str.length - 1];
// if the first and last characters are the same, check the rest of the string
if (first === last) {
let rest = str.slice(1, -1);
return isPalindrome(rest);
}
// if the first and last characters are not the same, the string is not a palindrome
else {
return false;
}
}
}
console.log(isPalindrome("racecar")); // true
console.log(isPalindrome("madam")); // true
console.log(isPalindrome("xyz")); // falseA power function takes a base and an exponent and returns the base raised to the exponent. For example, power(2, 3) returns 2 x 2 x 2 = 8.
function power(base, exponent) {
// base case: exponent is zero
if (exponent === 0) {
return 1;
}
// recursive case: exponent is positive
else {
return base * power(base, exponent - 1);
}
}
console.log(power(2, 3)); // 8A reverse function takes a string and returns the string with the characters in reverse order. For example, reverse(“hello”) returns “olleh”.
function reverse(str) {
// base case: str is empty
if (str === "") {
return "";
}
// recursive case: take the last character and append it to the reverse of the rest of the string
else {
let last = str[str.length - 1];
let rest = str.slice(0, -1);
return last + reverse(rest);
}
}
console.log(reverse("hello")); // "olleh"Quicksort is a sorting algorithm that uses recursion to divide and conquer the input array. It works by choosing a pivot element, partitioning the array around the pivot, and then recursively sorting the left and right subarrays.
// A function that partitions the array around the pivot
function partition(arr, start, end) {
// Taking the last element as the pivot
const pivotValue = arr[end];
let pivotIndex = start;
for (let i = start; i < end; i++) {
if (arr[i] < pivotValue) {
// Swapping elements
[arr[i], arr[pivotIndex]] = [arr[pivotIndex], arr[i]];
// Moving to next element
pivotIndex++;
}
}
// Putting the pivot value in the middle
[arr[pivotIndex], arr[end]] = [arr[end], arr[pivotIndex]];
return pivotIndex;
}
// A recursive function that sorts the array using quicksort
function quickSort(arr, start, end) {
// Base case or terminating case
if (start >= end) {
return;
}
// Returns pivotIndex
let index = partition(arr, start, end);
// Recursively apply the same logic to the left and right subarrays
quickSort(arr, start, index - 1);
quickSort(arr, index + 1, end);
}
// An example array to sort
let array = [7, -2, 4, 1, 6, 5, 0, -4, 2];
quickSort(array, 0, array.length - 1);
console.log(array); // [-4, -2, 0, 1, 2, 4, 5, 6, 7]If the recursion depth exceeds the maximum stack size, it can cause a stack overflow error and crash the program. Therefore, it is advisable to use recursion only when the problem can be solved with a reasonable number of recursive calls, and when the recursive function has a clear base case and termination condition.
Be mindful of the recursion depth and consider alternative approaches if necessary.
Iteration can often achieve the same result as recursion, but with less memory usage and faster execution. However, it may require more code and logic to implement, and may not be as intuitive or elegant as recursion.
For example, the factorial function can be written iteratively as:
// An iterative function that calculates the factorial of n
function factorial_iter(n) {
// Initialize the result as 1
let result = 1;
// Loop from 1 to n
for (let i = 1; i <= n; i++) {
// Multiply the result by i
result = result * i;
}
// Return the result
return result;
}
console.log(factorial_iter(5)); // 120Memoization is a technique of storing the results of previous function calls in a cache, and reusing them when the same input is encountered again.
It can improve the performance and efficiency of recursive functions, especially when they involve repeated or overlapping subproblems. However, memoization may increase the space complexity and require extra code to implement.
For example, the Fibonacci function can be written with memoization as:
// A memoized function that calculates the nth Fibonacci number
function fibonacci_memo(n, memo = {}) {
// Base case: if n is 0 or 1, return n
if (n == 0 || n == 1) {
return n;
}
// Check if the result is already in the cache
if (memo[n]) {
return memo[n];
}
// Recursive case: if n is greater than 1, return the sum of the previous two Fibonacci numbers
else {
// Calculate the result and store it in the cache
let result = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo);
memo[n] = result;
return result;
}
}Dynamic programming is a method of solving complex problems by breaking them down into simpler subproblems, and solving them in a bottom-up manner.
Dynamic programming can optimize the time and space complexity of recursive functions, by avoiding unnecessary recursive calls and storing the intermediate results in a table. However, dynamic programming may require more analysis and planning to identify the optimal substructure and overlapping subproblems of the problem.
For example, the coin change problem can be solved with dynamic programming as:
// calculates the minimum number of coins needed to make a given amount
function coinChange(coins, amount) {
// Initialize a table of size amount + 1 with infinity values
let table = new Array(amount + 1).fill(Infinity);
// Set the base case: the minimum number of coins to make 0 is 0
table[0] = 0;
// Loop from 1 to amount
for (let i = 1; i <= amount; i++) {
// Loop through each coin value
for (let coin of coins) {
// If the coin value is less than or equal to the current amount
if (coin <= i) {
// Update the table with the minimum of the current value and the previous value minus the coin value plus one
table[i] = Math.min(table[i], table[i - coin] + 1);
}
}
}
// Return the final value in the table, or -1 if it is infinity
return table[amount] == Infinity ? -1 : table[amount];
}
console.log(coinChange([1, 2, 5], 11)); // 3