Đệ quy

int factorial(int n)
{
    if (n <= 1)                     /* 1. điều kiện dừng */
        return 1;

    return n * factorial(n - 1);    /* 2. bước tiến về điều kiện dừng */
}

factorial(4)
  = 4 * factorial(3)
        = 3 * factorial(2)
              = 2 * factorial(1)
                    = 1                <- điều kiện dừng
              = 2 * 1  = 2
        = 3 * 2  = 6
  = 4 * 6  = 24

/* Đệ quy: đọc gần với định nghĩa toán học */
long long gt_de_quy(int n)
{
    return n <= 1 ? 1 : n * gt_de_quy(n - 1);
}

/* Lặp: tốn bộ nhớ hằng số */
long long gt_lap(int n)
{
    long long kq = 1;

    for (int i = 2; i <= n; ++i)
        kq *= i;

    return kq;
}

void hanoi(int n, char tu, char den, char tam)
{
    if (n == 0)
        return;

    hanoi(n - 1, tu, tam, den);
    printf("Chuyen dia %d: %c -> %c\n", n, tu, den);
    hanoi(n - 1, tam, den, tu);
}

/* Cách 1: đệ quy ngây thơ. Mỗi tầng sinh hai nhánh. */
long long fib_de_quy(int n)
{
    return n <= 1 ? n : fib_de_quy(n - 1) + fib_de_quy(n - 2);
}

/* Cách 2: vòng lặp. */
long long fib_lap(int n)
{
    long long a = 0, b = 1;

    for (int i = 0; i < n; ++i) {
        long long t = a + b;

        a = b;
        b = t;
    }

    return a;
}

/* Cách 3: đệ quy có nhớ. Mỗi giá trị chỉ tính đúng một lần. */
long long fib_memo(int n, long long *memo)
{
    if (n <= 1)          return n;
    if (memo[n] != -1)   return memo[n];

    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);

    return memo[n];
}

#include <string.h>

long long fib(int n)
{
    long long memo[95];

    memset(memo, -1, sizeof memo);   /* mọi byte bằng 0xFF nên mọi phần tử bằng -1 */

    return fib_memo(n, memo);
}

#include <stdio.h>

void vo_han(int n)
{
    printf("%d\n", n);
    vo_han(n + 1);
}

int main(void)
{
    vo_han(0);
    return 0;
}

/* Giới hạn độ sâu, cách làm chuẩn của trình phân tích cú pháp */
#define DO_SAU_TOI_DA 200

int phan_tich(const char *s, int do_sau)
{
    if (do_sau > DO_SAU_TOI_DA)
        return -1;                        /* từ chối thay vì sập */

    /* ... phan_tich(s_con, do_sau + 1) ... */

    return 0;
}

/* Không phải đệ quy đuôi: sau khi factorial(n-1) trả về, còn phải nhân với n */
int gt_thuong(int n)
{
    if (n <= 1) return 1;

    return n * gt_thuong(n - 1);
}

/* Đệ quy đuôi: kết quả tích lũy được mang theo trong tham số acc */
int gt_duoi(int n, int acc)
{
    if (n <= 1) return acc;

    return gt_duoi(n - 1, n * acc);      /* không còn gì để làm sau lời gọi này */
}

int la_le(int n);          /* bắt buộc có nguyên mẫu vì hai hàm gọi vòng nhau */

int la_chan(int n)
{
    return n == 0 ? 1 : la_le(n - 1);
}

int la_le(int n)
{
    return n == 0 ? 0 : la_chan(n - 1);
}