tailieunhanh - Đệ qui thuật toán đệ qui

Khái niệm. Từ "Đệ qui" xuất phát từ thuật ngữ "Recursion" có nghĩa là quay lại, lặp lại. Một đối tượng được gọi là đệ qui nếu nó bao gồm chính nó như một bộ phận hoặc nó được định nghĩa dưới dạng của chính Từ “đối tượng" cần hiểu theo nghĩa rộng, không nhất thiết. | Đệ qui Thuật toán đệ qui recursion Tư tưởng đệ qui Đệ qui Khái niệm Từ "Đệ qui" xuất phát từ thuật ngữ "Recursion" có nghĩa là quay lại, lặp lại. Một đối tượng được gọi là đệ qui nếu nó bao gồm chính nó như một bộ phận hoặc nó được định nghĩa dưới dạng của chính nó. - Từ “đối tượng" cần hiểu theo nghĩa rộng, không nhất thiết là đối tượng hàm hoặc phương thức. Thuật toán đệ qui Một thuật toán được gọi là đệ qui nếu nó giải bài toán bằng cách rút gọn liên tiếp bài toán ban đầu đến bài toán cũng tương tự như vậy nhưng có dữ liệu đầu vào nhỏ hơn. Ví dụ : Ðịnh nghĩa giai thừa của 1 số nguyên n là n!=1*2*3* (n-2)*(n-1)*n khi n>0 n!=1 khi n=0 n! có thể được định nghĩa bằng cách qui nạp như sau: 0! = 1, n! = n*(n-1)!, với mọi n > 0. Bài toán tính N! bây giờ thành tính N*(N-1)! Nhận xét Hàm (phương thức) được gọi là đệ qui nếu trong quá trình thực hiện nó tự gọi đến chính mình. đệ qui trực tiếp : Lời gọi có thể nằm bên trong hàm (phương thức), khi đó hàm (phương thức). đệ qui gián tiếp | Đệ qui Thuật toán đệ qui recursion Tư tưởng đệ qui Đệ qui Khái niệm Từ "Đệ qui" xuất phát từ thuật ngữ "Recursion" có nghĩa là quay lại, lặp lại. Một đối tượng được gọi là đệ qui nếu nó bao gồm chính nó như một bộ phận hoặc nó được định nghĩa dưới dạng của chính nó. - Từ “đối tượng" cần hiểu theo nghĩa rộng, không nhất thiết là đối tượng hàm hoặc phương thức. Thuật toán đệ qui Một thuật toán được gọi là đệ qui nếu nó giải bài toán bằng cách rút gọn liên tiếp bài toán ban đầu đến bài toán cũng tương tự như vậy nhưng có dữ liệu đầu vào nhỏ hơn. Ví dụ : Ðịnh nghĩa giai thừa của 1 số nguyên n là n!=1*2*3* (n-2)*(n-1)*n khi n>0 n!=1 khi n=0 n! có thể được định nghĩa bằng cách qui nạp như sau: 0! = 1, n! = n*(n-1)!, với mọi n > 0. Bài toán tính N! bây giờ thành tính N*(N-1)! Nhận xét Hàm (phương thức) được gọi là đệ qui nếu trong quá trình thực hiện nó tự gọi đến chính mình. đệ qui trực tiếp : Lời gọi có thể nằm bên trong hàm (phương thức), khi đó hàm (phương thức). đệ qui gián tiếp : nếu hàm (phương thức) gọi tới hàm (phương thức) khác, mà hàm (phương thức) này lần lượt gọi tới hàm (phương thức) ban đầu. Loại đệ qui Trực tiếp A A Gián tiếp A B B A Trực tiếp A A A A A A Gián tiếp A B A B A B . Như đã biết, một thuật toán được đòi hỏi phải thỏa mãn các tính chất: Tính xác định. Tính hữu hạn hay tính dừng. Tính đúng. Do tính chất của thuật toán là sau một số hữu hạn các phép toán thì thuật toán kết thúc,vì vậy thuật toán đệ qui phải gồm có 2 phần: phần đệ qui phần không đệ qui (phần cơ sở -phần làm dừng tính đệ qui) Phần cơ sở gồm các trường hợp không cần thực hiện lại thuật toán, tức là các trường hợp dừng mà ta có thể trực tiếp giải quyết được bài toán (hay không có yêu cầu gọi đệ qui). Ví dụ : tính N! thì trường hợp n=1 thì không cần tính nữa cơ sở Phần đệ quy là phần trong thuật toán có yêu cầu gọi đệ quy, tức là yêu cầu thực hiện lại thuật toán ở cấp độ thấp hơn. Trong phần đệ quy, yêu cầu gọi đệ qui thường được đặt trong một điều kiện kiểm tra việc gọi