Đệ quy

Khái niệm

Đệ quy là kỹ thuật trong đó một hàm gọi lại chính nó để giải quyết bài toán bằng cách chia thành các trường hợp nhỏ hơn cùng bản chất. Một lời giải đệ quy luôn cần ít nhất hai phần: trường hợp dừng và bước gọi tiếp.

Ví dụ tính giai thừa

def factorial(number):
		if number <= 1:
				return 1
		return number * factorial(number - 1)


print(factorial(5))

program RecursionDemo;

function Factorial(number: Integer): Integer;
begin
	if number <= 1 then
		Factorial := 1
	else
		Factorial := number * Factorial(number - 1);
end;

begin
	Writeln(Factorial(5));
end.

#include <stdio.h>

int factorial(int number) {
		if (number <= 1) {
				return 1;
		}
		return number * factorial(number - 1);
}

int main(void) {
		printf("%d\n", factorial(5));
		return 0;
}

#include <iostream>
using namespace std;

int factorial(int number) {
    if (number <= 1) {
        return 1;
    }
    return number * factorial(number - 1);
}

int main() {
    cout << factorial(5) << endl;
    return 0;
}

static int Factorial(int number) {
    if (number <= 1) return 1;
    return number * Factorial(number - 1);
}

Console.WriteLine(Factorial(5));

function factorial(number) {
    if (number <= 1) return 1;
    return number * factorial(number - 1);
}

console.log(factorial(5));

function factorial(number: number): number {
    if (number <= 1) return 1;
    return number * factorial(number - 1);
}

console.log(factorial(5));

package main

import "fmt"

func factorial(number int) int {
    if number <= 1 {
        return 1
    }
    return number * factorial(number-1)
}

func main() {
    fmt.Println(factorial(5))
}

fn factorial(number: u64) -> u64 {
    if number <= 1 {
        return 1;
    }
    number * factorial(number - 1)
}

fn main() {
    println!("{}", factorial(5));
}

Nguyên tắc thiết kế đệ quy

Kết quả của bài toán lớn phải được ghép đúng từ kết quả của bài toán nhỏ hơn.
Luôn cần có điều kiện dừng (base case) để tránh đệ quy vô hạn.
Mỗi lần gọi đệ quy phải tiến gần hơn tới điều kiện dừng.

Lưu ý

Đệ quy giúp cách diễn đạt lời giải tự nhiên hơn trong nhiều bài toán như cây, phân hoạch và duyệt cấu trúc lồng nhau. Tuy nhiên, nếu số lần gọi quá sâu, chương trình có thể tốn nhiều bộ nhớ ngăn xếp hơn cách lặp tương đương.

Ghi chú theo ngôn ngữ

Thông tin</div>

Python có giới hạn chiều sâu đệ quy mặc định (thường là 1000 tầng). Có thể dùng sys.setrecursionlimit() để tăng, nhưng cách tốt hơn là chuyển sang vòng lặp khi cần xử lý dữ liệu lớn.

Pascal hỗ trợ đệ quy, nhưng cần khai báo nguyên mẫu (forward declaration) nếu hai hàm gọi chéo nhau.

C không giới hạn chiều sâu đệ quy một cách tường minh, nhưng bộ nhớ ngăn xếp (stack) có hạn và đệ quy quá sâu sẽ gây lỗi stack overflow.

C++ cũng có nguy cơ stack overflow với đệ quy sâu. Trình biên dịch hiện đại có thể tối ưu hóa tail recursion trong một số trường hợp.

C# cho phép đệ quy nhưng không đảm bảo tối ưu hóa tail recursion. Nên giữ chiều sâu đệ quy hợp lý và xem xét dùng vòng lặp cho bài toán lớn.

JavaScript không đảm bảo tối ưu hóa tail call trên hầu hết engine. Với dữ liệu lớn, vòng lặp thường an toàn hơn về mặt bộ nhớ.

TypeScript kế thừa giới hạn runtime của JavaScript. Tương tự JS, nên cẩn thận với đệ quy sâu trong ứng dụng xử lý dữ liệu lớn.

Go không tối ưu tail recursion. Tuy nhiên, goroutine stack có thể mở rộng động, nên ít gặp stack overflow hơn so với C/C++.

Rust không đảm bảo tối ưu tail recursion. Stack overflow với đệ quy sâu sẽ gây panic. Dùng cấu trúc lặp hoặc thư viện stacker cho bài toán đòi hỏi chiều sâu lớn.

Kết luận

Đệ quy là công cụ tư duy quan trọng cho nhiều lớp thuật toán. DFS và các thuật toán chia để trị (merge sort, quick sort) trong mục Thuật toán đều dựa vào đệ quy. Trong mục Lý thuyết đồ thị, DFS đệ quy xuất hiện trong sắp xếp tô pô và kiểm tra đồ thị hai phía.

Trong series này: