Recursive Programming

Recursion in short can be described as a divide and conquer method of solving a problem in computer science. With the first step being to divide a problem into smaller subproblems then dividing those subproblems and so on. Until the problem cannot practically be divided down any more then solve the smallest subproblem then use that solution to go back up a level and solve the next smallest sub problem and so on until you arrive at the original solution. If graphed this process could be represent as a tree, with the trunk being the original problem and the branches being the subproblems and the leaves being their subproblems.

If you haven’t realized it probably the most difficult part about recursion is describing it while in practice it can be mind-bending at times overall it is pretty simple to implement. In fact, the idea of recursion is by no means exclusive to computer science nor a recently developed process being used back in 1888 by Dedekind to as notation to describe natural numbers (2). Recursion in general is more of a concept used in computer science classes and in older languages that don’t have built in for loops like scheme languages. It is a slightly slower method than many iterative methods of problem solving, and has some risk of stack overflow but can be used in production code if it is easier to conceptualize and therefor makes for quicker to develop, it is commonly used in tree or graph searches (3).

There are two key concepts every recursive function has the base case and the recursive case.

1. The base case: where the function checks if it’s in the smallest subproblem and then will return the solution. This must be checked for before the recursive case.
2. The recursive case: the case in which the function divides the problem, then inputs the subproblem into a function call of itself.

A simple example of a solution using recursion is solving a factorial.

function factorial(n) {
  // Base case
  if (n === 0 || n === 1) {
    return 1;
  }
  // Recursive case
  return n * factorial(n — 1);
}

For this example if you called factorial(3), the order of returns would look like this:

1. factorial(3) will return 3 * factorial(2)
2. factorial(2) will return 2 * factorial(1)
3. factorial(1) will return 1 (as n now equals 1)

So if we substitute:

1. factorial(3) returns 3(2*factorial(1))
2. factorial(3) returns (3(2(1))) = 6 (or 3! )

So the first call to return is factorial(1) which causes a chain reaction for all the other call to return till the final solution (5).

So, when designing a recursive function, the most important part is to first figure out the base case, which is usually just simple check then a return of a static value or the input value. For example, if doing tree traversal your base case checks if the node is null then just returns nothing if it is. Then find the recursive case which can be a little trickier but is usually just making one or two call to the same function with the input being some a modified version of the original input. In general recursion can seem confusing and daunting when first learning it as is something that is difficult to understand on paper but once you start writing some recursive programs it will seem much easier.

Check out this simple recursive Sudoku solver I wrote in java.

https://github.com/EricStukenberg/SudokuSolver

Sources:

1. https://ericstukenberginfo.data.blog/wp-content/uploads/2020/06/7bd81-1w2ljumwtkjgldz01qsqiyg.gif
2. https://en.wikipedia.org/wiki/Recursion_(computer_science)
3. http://www.people.cs.uchicago.edu/~soare/History/compute.pdf
4. https://arstechnica.com/civis/viewtopic.php?f=20&t=1142971#:~:text=Recursion%20is%20(in%20many%2C%20but,valuable%20tool%20for%20production%20code.
5. https://medium.com/@daniel.oliver.king/getting-started-with-recursion-f89f57c5b60e