Don't curse, recurse

Recursion is a concept in mathematics, computability theory, and computer programming, although the usage differs. In computability theory, a recursive set is one where membership can be confirmed or refuted using a process that terminates, and a recursively enumerable set is one for which there is a process that terminates if membership should be confirmed but may not terminate if membership should be refuted.  In mathematics, recursion refers to the embedding of something within itself, such as a function that uses itself in its own definition.  In computer programming, a recursive algorithm is a description of a computation that includes the same computation, but using different parameters.

We can define the factorial function recursively for integers greater than 0 as fact(n) = If n = 1 then 1 else (n fact(n-1)), where '=' means 'is defined as'.  Then we compute the factorial of 5 as

fact(5)                                   120
   |                                        ^
   v                                        |
  5 (fact(4) )                             5 (24)
        |                                      ^
        v                                      |
    5 (4 (fact(3) ) )                      5 (4 (6) )
             |                                   ^
             v                                   |
      5 (4 (3 (fact(2) ) ) )              5 (4 (3 (2) ) )
                  |                                ^
                  v                                |
        5 (4 (3 (2 (fact(1) ) ) ) )  ->  5 (4 (3 (2 (1) ) ) )
                       |                             ^
                       |=============================|

While descending into and ascending from level to level can illustrate simple cases, the best way to understand more complex recursion is to verify the requirements of a recursive procedure:  there must be one or more non-recursive cases and every recursive invocation of the procedure must invoke cases with simpler arguments, which means that there must be a finite number of recursive invocations; the non-recursive cases must produce the correct result; and the recursive steps will produce the correct result when the recursively invoked steps produce the correct result.

For example, the Quicksort algorithm sorts a list of more than one element by picking an element of the list (the pivot element), moving the elements smaller than the pivot element to the front of the list, and moving the elements larger than the pivot element to the back of the list, moving the pivot element between the front and back of the list, and, if any elements were moved, applying Quicksort to the front of the list, then applying Quicksort to the back of the list.  A list of one element (or zero elements) is already sorted, so Quicksort does nothing.

[70, 12, 56, 45, 98, 28, 84]                 Initial list
              ^                              Pivot
[[28, 12], 45, [56, 98, 70, 84]]             After first pass
       ^                                     New Pivot
[[[], 12, [28]], 45, [56, 98, 70, 84]]       After second pass
[[12, 28], 45, [56, 98, 70, 84]]             Combine second pass
                         ^                   New Pivot
[[12, 28], 45, [[56], 70, [98, 84]]]         After third pass
                                ^            New Pivot
[[12, 28], 45, [[56], 70, [[], 84, [98]]]]   After fourth pass
[[12, 28], 45, [[56], 70, [84, 98]]]         Combine fourth pass
[[12, 28], 45, [56, 70, 84, 98]]             Combine third pass
[12, 28, 45, 56, 70, 84, 98]                 Combine first pass
                                             (final list)

To verify the correctness of Quicksort we note that the list being sorted is smaller in each pass than in the previous pass, therefore there will be no more passes than there are elements in the list.  Because each pass of Quicksort moves elements less than the pivot element to the front of the list and elements greater than the pivot element to the back of the list then puts the pivot element between the lesser elements and the greater elements, the Quicksort of the front of the list sorts the front of the list and the Quicksort of the back of the list sorts the back of the list, so the Quicksort of the entire list sorts the entire list.