Mastering recursive functions in JavaScript

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:

  • Traversing tree structures (e.g., DOM, file systems)
  • Finding factorial values
  • Implementing searching algorithms (e.g., binary search)
  • Performing calculations on nested data structures

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.

Classic examples using recursion

Factorial of a number

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)); // 120

Fibonacci sequence

Fibonacci 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);

Check if palindrome

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"));     // false

Calculate power

A 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)); // 8

Reverse a string

A 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
  // 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) {
  // 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]

Alternative approaches to recursion

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.

Using iteration approach

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)); // 120

Using memoization technique

Memoization 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;

Using dynamic programming

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