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 ...