0. Mục tiêu học tập

Hàm đệ quy là hàm gọi chính nó trực tiếp hoặc gián tiếp thông qua một loạt câu lệnh. Đệ quy đóng một vai trò quan trọng trong lập trình. Trong nhiều trường hợp, các vấn đề có thể được giải quyết một cách dễ dàng với sự trợ giúp của đệ quy. Phần này chủ yếu giới thiệu các khái niệm cơ bản về đệ quy và cách xây dựng chương trình đệ quy.
Sau khi học xong phần này bạn cần nắm vững những nội dung sau:

• Hiểu các khái niệm cơ bản về đệ quy và các ý tưởng lập trình đằng sau đệ quy
• Tìm hiểu cách xây dựng chương trình đệ quy

1 đệ quy

1.1 Các khái niệm cơ bản về đệ quy

Đệ quy là một phương pháp giải bài toán liên tục chia bài toán thành các bài toán con nhỏ hơn và giải bài toán bằng cách xử lý các bài toán con chung. Hàm đệ quy là hàm gọi chính nó trực tiếp hoặc gián tiếp thông qua một loạt câu lệnh. Cần lưu ý rằng mỗi khi một hàm đệ quy gọi chính nó, nó sẽ đơn giản hóa bài toán ban đầu và cuối cùng chuỗi các bài toán nhỏ hơn phải hội tụ về trường hợp cơ sở, giải quyết bài toán và chấm dứt đệ quy. Đệ quy có thể được sử dụng để giải quyết các vấn đề phức tạp một cách rất dễ dàng. Nhiều hàm toán học được định nghĩa đệ quy, chẳng hạn như hàm giai thừa được định nghĩa đệ quy:
n ! = { 1 , n = 0 n ( n − 1 ) ! , n > 1 n! = \begin{cases} 1, & {n=0} \ n(n-1)!, & {n>1 } \end{cases}n!={1,n(n−1)!,n=0n>1

Mặc dù định nghĩa này là đệ quy nhưng nó không phải là một vòng lặp vô hạn không thể kết thúc. Trên thực tế, giai thừa có thể được tính rất đơn giản bằng cách sử dụng hàm này. Ví dụ, khi tính 3 ! 3! 3!, theo định nghĩa, 3 ! = 3 ( 3 – 1 ) ! = 3 ( 2 ! ) 3!=3(3–1) = 3(2!)3 !=3( 3–1)!=3(2!), tiếp theo chúng ta cần giải tìm 2 ! 2!2!, và áp dụng lại định nghĩa 3! = 4(2!) = 3[(2)(2 −1)!] = 3(2)(1!), hãy tiếp tục quá trình này và cuối cùng chúng ta cần tính 0! 0!0!, và theo định nghĩa 0!=10!=1, quá trình tính toán kết thúc:
3 ! = 3 ( 2 ! ) = 3 ( 2 ) ( 1 ! ) = 3 ( 2 ) ( 1 ) ( 0 ! ) = 3 ( 2 ) ( 1 ) ( 1 ) = 3(2!) = 3(2)(1!)= 3(2)(1)(0!)= 3(2)(1)(1)=63!=3(2!)=3(2)(1!)=3(2)(1)(0!)=3(2)(1)(1 )=6

Như bạn có thể thấy, định nghĩa đệ quy không phải là một vòng lặp vô hạn, bởi vì mỗi lần định nghĩa được áp dụng, chương trình sẽ chia bài toán thành các bài toán con đơn giản hơn, trong trường hợp ví dụ về hàm giai thừa, tính giai thừa của các số nhỏ hơn cho đến 0 !0!, có thể được giải quyết mà không cần áp dụng đệ quy. Khi đệ quy kết thúc, chúng ta nhận được một biểu thức đóng có thể được đánh giá trực tiếp, còn được gọi là "đệ quy"Tình huống cơ bản". Khi một hàm gọi chính nó để thực hiện một nhiệm vụ con, nó được gọi là "trường hợp đệ quy".

1.2 Tầm quan trọng của đệ quy

Hàm đệ quy là một kỹ thuật lập trình quan trọng được mượn từ toán học. Nói chung, việc sử dụng đệ quy có thể làm giảm đáng kể số lượng mã và rất hữu ích trong nhiều tác vụ có thể được phân tách thành các bài toán con, chẳng hạn như sắp xếp, duyệt và tìm kiếm. được thực hiện với sự trợ giúp của các phương pháp đệ quy cung cấp giải pháp nhanh chóng.

1.3 Ba nguyên tắc đệ quy

Giống như nhiều thuật toán, đệ quy cũng có những nguyên tắc quan trọng cần phải tuân theo, gọi là ba nguyên tắc đệ quy:

• Thuật toán đệ quy phải có trường hợp cơ sở;
• Các thuật toán đệ quy phải thay đổi trạng thái và hội tụ dần về trường hợp cơ sở;
• Các thuật toán đệ quy phải chứa các trường hợp đệ quy và có thể gọi chính chúng một cách đệ quy.

Cần lưu ý rằng ý tưởng cốt lõi của đệ quy không phải là lặp mà là chia bài toán thành các bài toán con nhỏ hơn và dễ giải quyết hơn.

1.4 Ứng dụng đệ quy

Đệ quy đóng một vai trò rất quan trọng trong lập trình Sau đây là một số tình huống thực tế mà đệ quy thường được sử dụng:

• Dãy số Fibonacci, tính giai thừa và các bài toán khác;
• Hợp nhất sắp xếp, sắp xếp nhanh chóng;
• tìm kiếm nhị phân;
• Truyền tải cây và đồ thị và các vấn đề liên quan;
• Tháp Hà Nội.

2 Ví dụ đệ quy

Trong phần này, chúng ta sẽ bắt đầu với một bài toán tổng danh sách đơn giản, xem cách sử dụng thuật toán đệ quy và sau đó tìm hiểu cách giải bài toán đệ quy cổ điển - Tháp Hà Nội.

2.1 Danh sách tổng hợp

Danh sách tổng hợp là một vấn đề rất đơn giản và nó hoàn hảo để hiểu ý tưởng của thuật toán đệ quy. Ví dụ chúng ta cần tính toán danh sách [1, 2, 3, 4, 5] Nếu sử dụng hàm vòng lặp để tính tổng, bạn có thể viết đoạn mã sau để tính tổng của tất cả các số trong danh sách:

def sum_list(list_data): result = 0 for i in range(list_data): result += i trả về kết quả

Làm cách nào để giải quyết vấn đề này mà không sử dụng vòng lặp? Chúng ta có thể viết quá trình tính tổng ( ( ( ( 1 + 2 ) + 3 ) + 4 ) + 5 ) ((((1+2)+3)+4)+5)((((1+2)+ 3 )+4)+5), và theo định luật giao hoán của phép cộng, quá trình tính toán cũng có thể được viết là ( 1 + ( 2 + ( 3 + ( 4 + 5 ) ) ) ) (1+(2+(3+(4+5))))(1+(2+(3+(4+5)))), thì ta thấy rõ rằng tổng của các dữ liệu trong danh sách Bằng đến phần tử đầu tiên của danh sách cộng với các phần tử còn lại:
sum_list (list_data) = list_data [0] + sum_list (list_data [1:]) sum_list(list_data)=list_data[0]+sum_list(list_data[1:])sum_list(list_data) =list_data[0]+sum_list(list_data[ 1:])
sử dụng trăn Việc thực hiện phương trình trên như sau:

def sum_list(list_data): if len(num_list) == 1: return list_data[0] else: return list_data[0] + sum_list(list_data[1:])

Trong mã, các điều kiện để hàm thoát được đưa ra trước tiên. Đây là tình huống cơ bản của hàm đệ quy. Trong ví dụ, nó có nghĩa là tổng các phần tử của một danh sách có độ dài bằng 1 là số trong danh sách. danh sách. Nếu điều kiện thoát không được đáp ứng,danh sách tổng hợp sẽ gọi chính nó. Đây là sự đệ quy của hàm đệ quy và lý do tại sao nó được gọi là hàm đệ quy.
Trong hình (a) bên dưới, bạn có thể thấy rằng giải pháp [1, 2, 3, 4, 5] kịp thờicuộc gọi đệ quythủ tục, mỗi lệnh gọi đệ quy sẽ giải quyết một vấn đề gần với trường hợp cơ bản hơn cho đến khi vấn đề không thể đơn giản hóa hơn nữa.
Khi không thể đơn giản hóa bài toán, hãy bắt đầu ghép lời giải của tất cả các bài toán con. Hình (b) bên dưới thể hiện hàm đệ quy. danh sách tổng hợp Thao tác cộng được thực hiện khi trả về kết quả của một loạt cuộc gọi, khi được trả về mức cao nhất sẽ giải quyết được vấn đề ban đầu.

2.2 Bài toán tháp Hà Nội

Tháp Hà Nội (Tháp Hà Nội) là một câu đố rất cổ điển. Nó bao gồm ba tòa tháp và nhiều đĩa có kích thước khác nhau có thể di chuyển đến bất kỳ cột nào. Bắt đầu với các đĩa được sắp xếp trên một tháp theo thứ tự kích thước tăng dần, với đĩa trên cùng là nhỏ nhất và đĩa dưới cùng là lớn nhất. Mục tiêu của câu đố là di chuyển các đĩa xếp chồng lên nhau sang một cột khác, tuân theo các quy tắc sau:

• Mỗi lần chỉ có thể di chuyển một đĩa;
• Đĩa lớn hơn không thể được đặt trên đĩa nhỏ hơn.

Tiếp theo chúng tôi giải thích cách sử dụng tháp trung gian phụ trợ, thay đổi chiều cao thành N một chồng đĩa từ tháp xuất phát Nguồn Di chuyển đến đích tháp Điểm đến:

• Với sự giúp đỡ của tháp thiết bị đầu cuối Điểm đến, di chuyển phần trên cùng n-1 đĩa từ Nguồn di chuyển đến phụ trợ;
• Tổng quan N đĩa từ Nguồn Tháp di chuyển đến tháp cuối Điểm đến;
• Với sự giúp đỡ của Nguồn tháp, ý chí n-1 đĩa từ tháp phụ phụ trợ Di chuyển đến tháp đích Điểm đến.

Bạn có thể thực hiện đệ quy các bước trên miễn là tuân thủ các quy tắc di chuyển Tháp Hà Nội. Tháp đơn giản nhất của Hà Nội là tháp chỉ có một tấm, trong trường hợp đó chỉ cần di chuyển tấm này đến cột cuối Điểm đến Vậy đó, đây là tình huống cơ bản. Các bước đệ quy trên sẽ giảm dần độ cao bằng cách N Chúng ta hãy tiến gần hơn đến tình huống cơ bản, như trong hình bên dưới:

Chìa khóa của thuật toán là thực hiện hai lệnh gọi đệ quy. Lần đệ quy đầu tiên là loại bỏ tất cả trừ đĩa cuối cùng khỏi đĩa. Nguồn Tháp chuyển sang tháp phụ phụ trợ . Sau đó di chuyển đĩa cuối cùng đến tháp cuối Điểm đến. Đệ quy thứ hai là di chuyển đĩa từ phụ trợ di chuyển đến Điểm đến:

def towerOfHanoi(số, nguồn=1, đích=3, phụ=2): nếu số >= 1: towerOfHanoi (số - 1, nguồn, phụ, đích) print("Di chuyển đĩa %d từ tháp %d sang tháp % d" % (số, nguồn, đích)) thápOfHanoi (số - 1, phụ, đích, nguồn) towerOfHanoi(number=3)

Đầu ra của chương trình trông như thế này:

Di chuyển đĩa 1 từ tháp 1 sang tháp 3 Di chuyển đĩa 2 từ tháp 1 sang tháp 2 Di chuyển đĩa 1 từ tháp 3 sang tháp 2 Di chuyển đĩa 3 từ tháp 1 sang tháp 3 Di chuyển đĩa 1 từ tháp 2 sang tháp 1 Di chuyển đĩa 2 từ tháp 1 sang tháp 3 2 tới tháp 3 Di chuyển đĩa 1 từ tháp 1 sang tháp 3