Đệ quy lồng (Nested Recursion)

Một ví dụ cho đệ quy lồng (Nested Recursion) là tính một hàm Ackermann, một hàm nổi tiếng trong lý thuyết tính toán:

#include <iostream>

int ackermann(int m, int n) {
    if (m == 0) {
        return n + 1;
    } else if (m > 0 && n == 0) {
        return ackermann(m - 1, 1);
    } else {
        return ackermann(m - 1, ackermann(m, n - 1));
    }
}

int main() {
    int m = 2, n = 3;
    std::cout << "Ackermann(" << m << ", " << n << ") = " << ackermann(m, n) << std::endl;
    return 0;
}

Đệ quy lồng: Hàm ackermann có lời gọi đệ quy lồng bên trong một lời gọi đệ quy khác. Điều này tạo ra một sự lồng nhau giữa các lời gọi đệ quy.

Kết luận

• Đệ quy nhị phân và đệ quy lồng có thể tương tự trong ngữ cảnh của một số bài toán nhưng cũng có thể khác nhau trong ngữ cảnh khác. Trong Fibonacci, cả hai đều tạo ra một cấu trúc cây đệ quy.
• Đệ quy nhị phân: Được định nghĩa rõ ràng với mỗi lời gọi hàm dẫn đến hai lời gọi hàm khác.
• Đệ quy lồng: Lời gọi đệ quy nằm bên trong một lời gọi đệ quy khác, có thể không giới hạn ở hai lời gọi đệ quy như đệ quy nhị phân.