Recursion is Recursion

There is an aspect of C which is common to most modern languages that we have not yet discussed. Nowhere have we disallowed this practice, but we haven't given an example of it yet either. This is recursion.

Throughout our discussion of the creation and use of functions, the function being called has always been different from the function doing the calling. This is not required. Indeed a function may call itself or may call another function that later calls it back.

There's another thing we can do that as we'll see is recursive. Namely, we can have structures that contain pointers to the same type of structure.

What is recursion? The flip, but at the same time quite serious, answer is that recursion is that which is recursive. A recursive definition is something that's defined in terms of itself. Let's take and example. The factorial function n! is defined to be the product of all the number from 1 to n. So 4!=(1)(2)(3)(4) and n!=(1)(2)(3)...(n-1)(n). For simplicity, we define 0!=1. Another way to define factorial is using recursion. We can define factorial this way:

0!=1
n!=(n)(n-1)! for all n>0.

Notice that we have defined the factorial of n in terms of the factorial of n-1. In other words, we have defined the factorial function in terms of itself.

Let's look at how we use this definition to compute 4!:

	4!=(4)(3!)
	3!=(3)(2!)
	2!=(2)(1!)
	1!=(1)(0!)
	0!=1

So working backwards:

	1!=(1)(0!)=(1)(1)=1
	2!=(2)(1!)=(2)(1)=2
	3!=(3)(2!)=(3)(2)=6
	4!=(4)(3!)=(4)(6)=24

so 4!=24.

Let's look at another example. The Fibonacci numbers are defined as the sequence 1, 1, 2, 3, 5, 8, 13, ... where each number is the sum of the two preceding numbers. We can define this recursively:

F(1)=1
F(2)=1
F(n)=F(n-1)+F(n-2) for all n > 2.

Using this definition we can find the 5th Fibonacci number as follows:

	F(5)=F(4)+F(3)
	F(4)=F(3)+F(2)
	F(3)=F(2)+F(1)
	F(2)=1
	F(1)=1
	F(3)=F(2)+F(1)=1+1=2
	F(4)=F(3)+F(2)=2+1=3
	F(5)=F(4)+F(3)=3+2=5

finding the 5th Fibonacci number to be 5.

Numerical function aren't the only things we can define recursively. We can define concepts as basic as strings recursively. Remember that as we've seen them so far strings are sequences of characters. In C, we adopt the convention that the end of the string is followed by a null byte ('\0'). Let's consider another way to define a string.

A string may be an empty string.
A string may be a character followed by a string.

So we would construct the string Bob by saying that Bob was the character B followed by the string ob. The string ob is the character o followed by the string b. The string b is the character b followed by the empty string.

In a very similar manner, we can define a list as:

A list may be empty.
A list may be an item followed by a list.

So the list 1,2,3,4 is the item 1 followed by the list 2,3,4. The list 2,3,4 is the item 2 followed by the list 3,4. The list 3,4 is the item 3 followed by the list 4. The list 4 is the item 4 followed by the empty list.

If we define the a function G as follows:

G(0)=1
G(n)=2*G(n-1)

what is G(5)?