Đệ quy là gì?

1. Đệ quy là gì?

Một đối tượng được mô tả thông qua chính nó được gọi là mô tả đệ quy.

Một bài toán mang tính chất đệ quy khi nó có thể được phân rã thành các bài toán nhỏ hơn nhưng mang cùng tính chất với bài toán ban đầu, các bài toán nhỏ lại được phân rã thành các bài toán nhỏ hơn nữa.

Trong đời sống, ta cũng thường xuyên thấy một số hiện tượng đệ quy, ví dụ như hai chiếc gương đặt đối diện nhau, vòng xoắn ốc (trong vòng xoắn ốc có vòng xoắn ốc nhỏ hơn).

2. Hàm đệ quy là gì?

Trong lập trình, một hàm được gọi là đệ quy khi nó gọi chính nó trong thân hàm.

Ví dụ:

function Recusion(){
    Recusion();
}

Hàm đệ quy không thể gọi tới nó mãi, cần phải có một điểm dừng (còn gọi là điểm neo) tại một trường hợp đặc biệt, gọi là trường hợp suy biến (degenerate case).

Ví dụ:

function Factorial($n){
    // Điều kiện dừng
    if ($n == 0){
        return 1;
    }else{
        return $n * Factorial($n - 1); // Đệ quy tuyến tính
    }
}

Bạn phải hiểu rằng khi một hàm được gọi, nó sẽ được đưa vào Stack, hàm đệ quy cũng vậy, mỗi lần gọi chính nó thì nó lại được đưa vào Stack, nếu như không có điểm dừng, hoặc gọi mãi mà chưa tới điểm dừng, sẽ dễ xảy ra tình trạng tràn bộ nhớ Stack.

Profile photo of adminTheHalfHeart

B.V.T

Sinh ra và lớn nên ở Bắc Giang. Hiện tại thì tôi đang là một lập trình viên tại VietISO. Tôi lập website này với mục đích là bookmark những gì tôi đã đọc qua và mong muốn chia sẻ những gì tôi biết.