Trước tiên, cùng xem xét bài toán chứng minh sau: Chứng minh đẳng thức dưới đây đúng với mọi n∈N∗:n∈N∗:
1+3+5+⋯+(2n−1)=n2 (1)1+3+5+⋯+(2n−1)=n2 (1)
Ở bậc trung học cơ sở, ta đã biết về phương pháp quy nạp toán học dùng để chứng minh một đẳng thức hoặc bất đẳng thức đúng. Áp dụng phương pháp này, ta có thể giải quyết bài toán trên một cách dễ dàng:
1+3+5+⋯+(2k−1)+[2.(k+1)−1]=(k+1)21+3+5+⋯+(2k−1)+[2.(k+1)−1]=(k+1)2
Thật vậy, từ đẳng thức (2)(2) ta có:
1+3+5+⋯+(2k−1)+[2.(k+1)−1]=k2+[2.(k+1)−1]1+3+5+⋯+(2k−1)+[2.(k+1)−1]=k2+[2.(k+1)−1]
=k2+2k+1=(k+1)2=k2+2k+1=(k+1)2
Vậy đẳng thức (1)(1) đúng với n=k+1,n=k+1, tức là nó đúng với mọi n∈N∗n∈N∗.
Một cách tổng quát, quy nạp toán học là việc chứng minh một tính chất nào đó ứng với các số tự nhiên bằng cách chứng minh tính chất đó đúng với một vài trường hợp cơ sở (thường là chứng minh nó đúng với 00 hoặc 11), sau đó chứng minh nó đúng với nn bất kỳ nếu như giả sử rằng nó đúng với mọi số tự nhiên nhỏ hơn nn. Những bài toán như vậy rất phổ biến không chỉ trong Toán học, mà còn trong Tin học, đặc biệt là trong các bài toán tìm công thức Toán học. Tuy nhiên, chúng ta sẽ nói kĩ hơn về vấn đề này trong một chuyên đề khác.
Ta gọi một đối tượng là có tính đệ quy nếu như nó được định nghĩa thông qua chính nó hoặc thông qua một số đối tượng nhỏ hơn nó nhưng có cùng dạng với nó. Cùng xét vài ví dụ để làm rõ:
n!={1,neˆˊu n=0.(n−1)!×nneˆˊu n>0.n!={1,(n−1)!×nneˆˊu n=0.neˆˊu n>0.
Phương pháp định nghĩa như trên gọi là phương pháp đệ quy. Có rất nhiều đối tượng trong Toán học được định nghĩa theo kiểu như vậy.
Một bài toán PP được gọi là có tính chất đệ quy khi lời giải của nó có thể đưa về lời giải của bài toán P′P′ nhỏ hơn nó và có dạng giống nó, đồng thời lời giải của P′P′ không cần dùng tới PP. Lời giải cho những bài toán như vậy được gọi là giải thuật đệ quy. Bản chất của giải thuật đệ quy là phân tách một bài toán lớn thành những bài toán nhỏ hơn và dễ giải hơn, sau đó tìm cách kết hợp lời giải của các bài toán nhỏ lại thành lời giải cho bài toán lớn ban đầu. Bài toán tìm giai thừa của nn ở bên trên chính là một ví dụ cơ bản nhất cho các bài toán có tính chất đệ quy.
Giữa quy nạp toán học và giải thuật đệ quy có một mối quan hệ rất khăng khít: Nếu như ở quy nạp toán học, ta chứng minh một tính chất toán học dựa vào việc chứng minh nó đúng với một số trường hợp cơ sở rồi chứng minh nó đúng với mọi số tự nhiên nn dựa trên việc nó đã đúng với mọi số tự nhiên nhỏ hơn n;n; thì ở giải thuật đệ quy, chúng ta cũng tìm lời giải cho những bài toán cơ sở (thường rất đơn giản) trước, sau đó tìm cách cài đặt sao cho lời giải của bài toán lớn được suy ra từ lời giải của các bài toán nhỏ hơn tương tự như thế.
Như đã nói ở phần trước, với những bài toán có tính chất đệ quy, sau khi phân tách chúng về bài toán nhỏ hơn, chúng ta sẽ có hai nhiệm vụ:
Trong khi bước thứ nhất khá đơn giản vì bài toán cơ sở là bài toán có kích thước nhỏ, rất dễ giải, thì bước thứ hai là bước cần có nhiều tư duy hơn. Hệ thức dùng để liên hệ giữa các bài toán nhỏ và bài toán lớn được gọi là công thức truy hồi. Chúng ta gặp rất nhiều những định nghĩa về công thức truy hồi trong Toán học, lấy ví dụ:
Việc xác định công thức truy hồi của một bài toán có bản chất đệ quy là vấn đề quyết định đến việc có thể giải được nó hay không. Các lời giải đệ quy có thể sử dụng hai cách cài đặt là cài đặt đệ quy và cài đặt không đệ quy, ở phần sau chúng ta sẽ cùng nghiên cứu cách cài đặt các hàm đệ quy để giải bài toán có bản chất đệ quy.
You need to login in order to like this post: click here
YOU MIGHT ALSO LIKE
