1. Đệ quy là gì ?

Một đối tượng được gọi là đệ quy nếu nó được mô tả thông qua định nghĩa của chính nó. Nghĩa là, các đối tượng này được định nghĩa một cách quy nạp từ những khái niệm đơn giản nhất cùng dạng với nó. Trong toán học và tin học có rất nhiều đối tượng như thế. VD :

– Số tự nhiên được định nghĩa như sau :

  • 0 là một số tự nhiên
  • Nếu k là một số tự nhiên thì k+1 cũng là một số tự nhiên

Theo đó, ta sẽ có : 1=0+1 là số tự nhiên, 2=1+1 cũng là một số tự nhiên,….Cứ như vậy ta sẽ định nghĩa được các số tự nhiên khác lớn hơn. Do đó, số tự nhiên là khái niệm mang bản chất đệ quy.

– Định nghĩa giai thừa của n (n!) :

  • Khi n=0, ta có 0!=1
  • Khi n>0, ta có n!=(n-1)! x n

Như vậy, ta suy ra : 1! = 0! x 1, 2! = 1! x 2,… –> giai thừa cũng là một khái niệm mang tính đệ quy.

2. Bài toán đệ quy

Đó là những bài toán mang bản chất đệ quy. Nghĩa là những bài toán này có thể được phân rã thành các bài toán nhỏ hơn, đơn giản hơn nhưng có cùng dạng với bài toán ban đầu. Những bài toán nhỏ lại được phân rã thành các bài toán nhỏ hơn. Cứ như vậy, việc phân rã chỉ dừng lại khi bài toán con đơn giản đến mức có thể suy ra ngay kết quả mà không cần phải phân rã nữa. Ta phải giải tất cả các bài toán con rồi kết hợp các kết quả đó lại để có được lời giải cho bài toán lớn ban đầu. Cách phân rã bài toán như vậy gọi là “chia để trị” (devide and conquer), là một dạng của đệ quy.

3. Đệ quy trong lập trình

Một hàm được gọi là đệ quy nếu bên trong thân nó có một lời gọi đến chính nó. Nghe có vẻ vô lý nhỉ ? Một hàm làm sao có thể gọi nó mãi được, vì nếu như vậy sẽ sinh ra một vòng lặp vô tận. Nhưng trong thực tế, một hàm đệ quy luôn có điều kiện đừng được gọi là “điểm neo”. Khi đạt tới điểm neo, hàm sẽ không gọi chính nó nữa.

Khi được gọi, hàm đệ quy thường được truyền cho một tham số, thường là kích thước của bài toán lớn ban đầu. Sau mỗi lời gọi đệ quy, tham số sẽ nhỏ dần, nhằm phản ánh bài toán đã nhỏ hơn và đơn giản hơn. Khi tham số đạt tới một giá trị cực tiểu (tại điểm neo), hàm sẽ chấm dứt.

Trong lập trình, một bài toán muốn giải quyết bằng đệ quy thì bản thân nó phải là một bài toán đệ quy. Tức là bài toán đó có thể được đưa về bài toán cùng dạng nhưng đơn giản hơn.