2. Rekursjon

2.1 Fakultet

x! = 1 * 2 * 3 * 4 * .... * x
x! = x * (x - 1)!    // x-fakultet er lik x ganget med fakultet av x-1. Denne definisjonen er rekursiv, dvs. at den "kaller seg selv". For å finne fakultet av et tall, må vi altså finne fakultet av tallet under dette, og for å finne det, av tallet under det igjen. For at definisjonen ikke skal bli meningsløs ved bare å "kalle seg selv" og aldri terminere, må vi ha en base case:
1! = 1

Da ser vi at:
2! = 2 * (1!) = 2*1 = 2
3! = 3 * (2!) = 3*2 = 6
4! = 4 * (3!) = 4*6 = 24, osv ...
 

2.2 Fibonacci

Fibonacci-rekken er også rekursivt definert:
F(N) = F(N-1) + F(N-2), det vil si at hvert tall er lik summen av de to foregående tallene.
Her er base case
F(0) = 1, F(1) = 1, slik at rekken blir seende slik ut:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ..
(Man kan godt definere andre base cases, og da få andre Fibonacci-rekker.)

Rekursiv implementasjon av Fibonacci-rekken.
Ikke-rekursiv implementasjon av Fibonacci-rekken.
 

2.3 Et lite program-eksempel i C

Vi har satt oss fore å skrive ut et tall på skjermen, men kan bare skrive ett siffer om gangen. Hvordan skal vi klare å skrive ut tallet riktig? Her er en liten funksjon som er rekursiv: 
void PrintOut( int N ) {
    if (N >= 10) PrintOut(N/10); // base case: når N endelig er mindre enn 10, ellers kaller funksjonen seg selv
    printDigit( N % 10);         // i ti-tallssystemet gir dette det siste sifferet
}
PrintDigit er en funksjon som skriver et siffer på skjermen, noe a la: 
void PrintDigit( int N ) {
    putchar ( N + '0' );
}
 

2.4 Fire regler for rekursive programmer

(Kilde: Weiss.)
1. Base cases. Du må alltid ha en "base case" som kan bli løst uten rekursjon (ellers blir definisjonen meningsløs, og programmet vil aldri stoppe.)
2. Making progress. De rekursive kallene må alltid nærme seg base case.
3. Design rule. Gå ut ifra at alle de rekursive kallene virker.
4. Compound interest rule. Aldri dupliker arbeid ved å løse samme oppgave i forskjellige rekursive kall.