Introduction to Recursion

Recursion is a phenomenon where something is defined in terms of itself. In computer science, recursion refers to a function that calls itself as part of its definition. In the sense of divide and conquer, recursion poses the opportunity to solve a complex problem in smaller, simple steps. So far, our understanding of SQL without recursion implies that a query terminates since SQL cannot loop forever. At the same time, we know that any SQL query can be evaluated efficiently in$\mathcal{O}(r^c)$with$r$number of rows and$c$number of columns (that is, with polynomial effort). Adding recursion to SQL torpedoes these assumptions, however. We can no longer assume a query to terminate since recursion can introduce infinite loops. We cannot be sure about the efficiency of computations of polynomial complexity. Regardless, SQL makes this compromise, becoming a Turing-complete general-purpose programming language with recursion as the vehicle.

A practical example of recursion

Given this promise, we will illustrate the benefit of recursive computation based on the Fibonacci numbers. The Fibonacci sequence is a series of numbers that starts with 0 and 1, and each subsequent number is the sum of the two preceding it.

Mathematically, the Fibonacci numbers are defined as $f_n=f_{n−1}+f_{n−2}$ for $n\ge 3$, and as $f_1=f_2=1$ otherwise. This means that the $n$^th Fibonacci number can be computed by adding the $(n−1)$^th and $(n−2)$th Fibonacci numbers.

From a programming language perspective, like TypeScript, we know that the Fibonacci numbers can be computed iteratively and recursively. Iterative computation uses a loop to calculate each number in turn, while recursive computation involves calling a function that calls itself until the desired number is reached.