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.

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 |

1!=(1)(0!)=(1)(1)=1 | |

2!=(2)(1!)=(2)(1)=2 | |

3!=(3)(2!)=(3)(2)=6 | |

4!=(4)(3!)=(4)(6)=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 |

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.

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.

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