Cơ bản về thuật toán đệ quy
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ữ...
