Recursion - Part I - Beginners

A technique that is often neglected, Recursion can be a beautiful way to solve certain classes of problems. I will try to explain recursion in a way that involves many examples being the basis for truly "getting it." As this will be too long of a topic for just one article; this will just be part 1 out of a bigger series.

So what is Recursion?

Recursion is a technique where a function calls itself to solve a problem by breaking it down into smaller problems.

As you can imagine, something that calls itself over and over again will go on infinitely. This however isn't the same as a video game loop going on forever; recursive calls keep adding to the call stack. For the most part, each recursive call, will be added to the call stack until the recursion comes to a halt.

Since we don't have infinite memory or an infinitely sized call stack, we must then include a base case.

A base case is a condition that stops the recursive function from calling itself. When a recursive call reaches its base case, the last function will return without calling itself. This then pops the function off the call stack which then takes us back to the previous function call. This previous function then gets popped off the call stack again. This repeats until we have no more of its recursive function calls left on the stack.

Why Use Recursion?

Recursive solutions may sometimes be easier to both conceptualize and code up than an iterative approach. Its real strength lies in tackling problems in which the subproblem represents the same structure as the main problem. What do I mean by this? Take for instance the task of reversing a word. There are many ways one might approach this, but here's a recursive approach:

const reverseStr = (str) => {
  //base case to stop the recursion
  if (str=='' || str.length <= 1){ return str; }
  // recursive call that reduces the problem each time
  return reverseStr(str.substr(1)) + str.charAt(0);
}
console.log(reverseString('test')); //tset
console.log(reverseString('r')); //r
console.log(reverseString('tariq')); //qirat
console.log(reverseString('racecar')); //racecar
console.log(reverseString('bob')); //bob

Each time a recursive call is made, we are reducing the problem. Each smaller problem is of the same structure as the original problem. Here we are creating a substring of the word starting at index 1 to the end, while also appending the first character at index 0 to the end. We then call this function again with the substring. If you mentally visualize this process you will see that the string will get reversed in this fashion:

test becomes reverseStr('est') + 't'
which becomes reverseStr('st') + 'e' + 't'
which becomes reverseStr('t') 's' + 'e' + 't'
which hits the base case and becomes 't' + 's' + 'e' + 't'

After all the function calls get popped off the stack, we now get 't' + 's' + 'e' + 't' = 'tset' being returned by the first function call before being popped of the call stack and returning to whatever called the function, in this case the console.log().

As you can see there is a certain engineering elegance in solving a problem by solving the problems that comprises the original problem.

Now let's look at more examples to hone our intuition on seeing the recursive substructures within certain problems.

Palindrome

A palindrome is a word or other sequence of characters that is the same forwards and backwards. For example in the reverse string example I listed above, the words 'racecar' and 'bob' were the same when reversed. This indicates that they are palindromes. By thinking of how we approached reversing a string, we can come up with a similar approach to identify palindromes. Namely, the substructure of a palindrome is, you guessed it, a palindrome.

For racecar to be a palindrome, that means that aceca has to also be a palindrome, which means that cec has to be a palindrome, which means that e has to be a palindrome.

This insight into a palindrome's recursive sub structure is how we can approach coming up with a recursive solution. Here we simply just compare the first and last characters of a word. If they are the same, then we call the function again this time ignoring the first and last characters. Here we are breaking up the problem into its sub problems until we hit one of the base cases:

1. A single character is by definition a palindrome as it is read the same forwards and backwards.
2. If at any time, a recursive sub problem is identified to not be a palindrome, we can stop the recursion as for the original word to be a palindrome, its sub strings must also be palindromic.

const isPalindrome = (str) => {
  if (str.length <= 1){ return true; }
  const lastElement = str[str.length -1];
  //base case that only executes if a subproblem
  //is not a palindrome, which indicates the 
  //original problem is not a palindrome
  if (str[0] != lastElement ){return false };
  //recursive call
  return isPalindrome(str.slice(1,-1))

}
console.log(isPalindrome('racecar')); // true
console.log(isPalindrome('bob')); // true
console.log(isPalindrome('false')); // false
console.log(isPalindrome('tariq')); // false

File directory

Now you might be thinking, why are file directories listed as a recursive example? Because for the most part, a file system either has files or directories/folders. And in each folder could lie more files and folders. And in those folders could lie more files or folders. See the recursive structure? This insight allows us to easily build a directory file system scanner.

import path from 'node:path';
import fs from 'node:fs';

const  traverseDirectory = (dir) => {
  try{
    const files = fs.readdirSync(dir);
    files.forEach(file => {
      const filePath = path.join(dir, file);
      const stats = fs.statSync(filePath);
      
      if (stats.isDirectory()) {
        //If it is a directory, log it and recursively call
        //traverseDirectory() to dig deeper
        console.log(`Directory: ${filePath}`);
        traverseDirectory(filePath);
      } else {
        //If it is a file, log it
        console.log(`File: ${filePath}`);
      }
    });
  } catch(e){
    console.log(`The error ${e} has occurred.`)
  }
}
traverseDirectory('/Users/tariqshams/Documents/Playgrounds/');
//Prints out:
// Directory: /Users/tariqshams/Documents/Playgrounds/TestDirectory
// File: /Users/tariqshams/Documents/Playgrounds/TestDirectory/Dummy.file
// File: /Users/tariqshams/Documents/Playgrounds/test.js

Many file systems in fact used/still use B-Trees as an underlining data structure that is recursive in nature. I will discuss more about trees and other discrete math / graph theory content in a follow up series.

Now to conclude part I with two standard recursive problems. These are defined recursively in math and thus are some of the perfect computer science algorithms to implement recursively.

Fibonacci Sequence

Here is a classic problem along with factorials that is defined recursively in math.

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones.

Expressed mathematically,

f(n) = f(n-1) + f(n-2)

where f(0) = 0 and f(1) = 1 by definition.

So it starts with 0 and 1, and the sequence goes: 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on.

const fibonacci = (n) => {
  // Base case: if n is 0 return 0, if n is 1 return 1
  if (n <= 1) { return n; }
  // Recursive case: sum of the two preceding numbers
  return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(8)); // 21

Factorials!

Just like the fibonacci sequence, we can define factorials mathematically. the factorial of a number n, notated as n! is given by:

n! = n * n-1 * n-2 * n-3 * ... * 1

also 0! = 1! = 1

From this we can see that it is trivial to derive the recursive implementation.

const factorial = (n) => {
  if ( n<=1 ){ return 1; }
  return factorial(n-1) * n
}
console.log(factorial(3)) // 6
console.log(factorial(5)) // 120

Stay tuned for the follow up parts of the series. There I will cover Tail Call Optimization, Trampolines, Memoization, Dynamic Programming, Backtracking, Binary tree traversals, n-ary tree traversals and famous problems such as the tower of Hanoi, the Josephus problem and more.