recursion by vdamewood

CC-BY-4.0
Recursion:

A recursive process is a process that can be expressed by using itself as
a step. One case of recursion can be used to describe the process of
calculating factorials. The factorial of a number is the product of
multiplying all of the numbers from one to that number. For example, the
factorial of 5 is 1 * 2 * 3 * 4 * 5, which is 120. Because a factorial is
calculated as the product of all the numbers below it, it can also be
calculated as a number, multiplies by the factorial of the number just below
it. To extend the previous example, since the factorial of 4 is 1 * 2 * 3 * 4,
the factorial of five is just five times that. Thus, if we set the factorial
of one to one itself, then we can express all factorials as the product of
n times the factorial of n-1. We would write this as a C function like this:

factorial(int n)
{
	if (n == 1)
		return 1;
	else
		return factorial(n-1)*n;
}

Another form of recursion is called tail recursion. With tail recursion, the
the last step of using a process is to reuse the process itself. The above
example, for calculating factorials is not tail recursive. The reason is that
when you call factorial again, you still have one more step once you get its
result. You still have to multiply its result by your current number.

For an example of a tail recursive process, consider the process of
calculating the greatest common divisor of two numbers. If you have two
numbers, a and b, through a trick of math, the greatest common divisor of
the two numbers is also the greatest common divisor of b, and the remainder of
divind a by b, unless they evenly divide, in which case you already have your
answer. In C, we use % as a special symbol for the modulo operator, which
yeilds the remainder in division. The process can be expressed with this C
function:

int gcd(int a, int b)
{
	if b == 0
		return a;
	else
		return gcd(b, a % b);
}

If a and b evenly divide, then the remainder of dividing them will be zero,
in which case the other value is the answer. If they don't divide evenly, we
can call gcd again on the new values, to get the correct result. Consider this
example, 9 and 12.

The first time we call this function, a will be 9, and b will be 12. Since b
is not zero, call gcd(12, 9 % 12), where 9 % 12 is 9. This first step effectly
swaps the values so that a is the greater value and b is the lower. Now we
have gcd(12, 9). 12 % 9 is 3. So we try again with 9, and 3. With gcd(9, 3) we
get another call of gcd(3, 0). Since b is 0, we return 3, and since each
call is just returning the value return by the next call, they all end up
returning 3.

Recursive functions are popular because they can be proven correct to solve
certain problems through a process called proof by mathematical induction. In
its simplest terms, you prove some base case, like the factorial of 1 is 1,
and then you prove a case such that if one step is true, then that implies the
next step is true. Such as showing that a factorial of n is the factorial of
n-1 times n. By showing that these are correct, we can show that the factorial
function works for all numbers from one to infinity. By doing it this way, bugs
are easier to find, be cause we have reduced an infinite number of cases to
just two. Tail recursion has the added benefit that since your just returning
a value from a function call, the compiler can translate to simpler code that
simply goes back to the beginning of the function, rather than by actually going
through the slightly longer process of calling the function again.