Hàm đệ quy trong C. Đệ quy và thuật toán đệ quy
Đệ quy là khi một chương trình con gọi chính nó. Khi lần đầu tiên đối mặt với việc xây dựng thuật toán như vậy, hầu hết mọi người đều gặp những khó khăn nhất định, nhưng chỉ cần thực hành một chút, đệ quy sẽ trở nên rõ ràng và rất dễ hiểu. công cụ hữu ích trong kho vũ khí lập trình của bạn.
1. Bản chất của đệ quy
Một thủ tục hoặc hàm có thể chứa các lệnh gọi đến các thủ tục hoặc hàm khác. Thủ tục cũng có thể gọi chính nó. Không có nghịch lý nào ở đây - máy tính chỉ thực hiện tuần tự các lệnh mà nó gặp trong chương trình và nếu gặp lệnh gọi thủ tục, nó chỉ cần bắt đầu thực hiện thủ tục này. Không quan trọng thủ tục nào đưa ra lệnh để thực hiện việc này.
Ví dụ về thủ tục đệ quy:
Thủ tục Rec(a: số nguyên); bắt đầu nếu a>
Hãy xem điều gì sẽ xảy ra nếu một lệnh gọi, chẳng hạn, có dạng Rec(3) được thực hiện trong chương trình chính. Dưới đây là sơ đồ thể hiện trình tự thực hiện của các câu lệnh.
Cơm. 1. Sơ đồ khối của thủ tục đệ quy.
Thủ tục Rec được gọi với tham số a = 3. Nó chứa lệnh gọi thủ tục Rec với tham số a = 2. Cuộc gọi trước đó vẫn chưa hoàn thành, vì vậy bạn có thể tưởng tượng rằng một thủ tục khác được tạo và thủ tục đầu tiên không hoàn thành công việc của nó cho đến khi nó kết thúc. Quá trình gọi kết thúc khi tham số a = 0. Tại thời điểm này, 4 trường hợp của thủ tục được thực thi đồng thời. Số lượng các thủ tục được thực hiện đồng thời được gọi là độ sâu đệ quy.
Thủ tục thứ tư có tên (Rec(0)) sẽ in số 0 và hoàn thành công việc của nó. Sau đó, điều khiển quay lại thủ tục đã gọi nó (Rec(1)) và số 1 được in, v.v. cho đến khi tất cả các thủ tục được hoàn thành. Kết quả cuộc gọi ban đầu sẽ in ra bốn số: 0, 1, 2, 3.
Một hình ảnh trực quan khác về những gì đang xảy ra được hiển thị trong Hình. 2.
Cơm. 2. Thực hiện thủ tục Rec với tham số 3 bao gồm thực hiện thủ tục Rec với tham số 2 và in số 3. Ngược lại, thực hiện thủ tục Rec với tham số 2 bao gồm thực hiện thủ tục Rec với tham số 1 và in số 2. V.v. .
BẰNG bài tập độc lập hãy nghĩ xem điều gì sẽ xảy ra khi bạn gọi Rec(4). Ngoài ra, hãy xem xét điều gì sẽ xảy ra nếu bạn gọi thủ tục Rec2(4) bên dưới, với các toán tử bị đảo ngược.
Thủ tục Rec2(a: số nguyên); bắt đầu viết(a); nếu a>0 thì Rec2(a-1); kết thúc;
Xin lưu ý rằng trong các ví dụ trên, lệnh gọi đệ quy nằm bên trong điều hành có điều kiện. Cái này Điều kiện cần thiếtđể sự đệ quy kết thúc. Cũng lưu ý rằng thủ tục sẽ tự gọi chính nó với một tham số khác với tham số mà nó được gọi. Nếu quy trình không sử dụng biến toàn cục thì điều này cũng cần thiết để đệ quy không tiếp tục vô thời hạn.
Có thể hơn một chút mạch phức tạp: Hàm A gọi hàm B, hàm này gọi hàm A. Hàm này được gọi là đệ quy phức tạp. Hóa ra thủ tục được mô tả trước tiên phải gọi một thủ tục chưa được mô tả. Để thực hiện được điều này, bạn cần sử dụng .
Thủ tục A(n: số nguyên); (Mô tả chuyển tiếp (tiêu đề) của thủ tục đầu tiên) thủ tục B(n: số nguyên); (Mô tả chuyển tiếp thủ tục thứ hai) thủ tục A(n: số nguyên); ( Mô tả đầy đủ thủ tục A) bắt đầu writeln(n); B(n-1); kết thúc; thủ tục B(n: số nguyên); (Mô tả đầy đủ quy trình B) bắt đầu writeln(n); nếu n
Một khai báo chuyển tiếp của thủ tục B cho phép nó được gọi từ một thủ tục A. Một khai báo chuyển tiếp của thủ tục A trong trong ví dụ này không bắt buộc và được thêm vào vì lý do thẩm mỹ.
Nếu đệ quy thông thường có thể được ví như ouroboros (Hình 3), thì hình ảnh của đệ quy phức tạp có thể được rút ra từ bài thơ thiếu nhi nổi tiếng, trong đó “Những con sói sợ hãi và ăn thịt lẫn nhau”. Hãy tưởng tượng hai con sói ăn thịt lẫn nhau và bạn sẽ hiểu được đệ quy phức tạp.
Cơm. 3. Ouroboros – con rắn tự nuốt chửng cái đuôi của mình. Trích từ luận thuyết giả kim thuật “Synosius” của Theodore Pelecanos (1478).
Cơm. 4. Đệ quy phức tạp.
3. Mô phỏng vòng lặp bằng đệ quy
Nếu một thủ tục gọi chính nó, về cơ bản nó sẽ khiến các lệnh chứa trong đó được thực thi lại, tương tự như một vòng lặp. Một số ngôn ngữ lập trình hoàn toàn không chứa các cấu trúc vòng lặp, khiến các lập trình viên phải tổ chức các lần lặp lại bằng cách sử dụng đệ quy (ví dụ: Prolog, trong đó đệ quy là một kỹ thuật lập trình cơ bản).
Ví dụ: hãy mô phỏng công việc vòng lặp for. Để làm điều này, chúng ta cần một biến bộ đếm bước, có thể được triển khai, chẳng hạn như một tham số thủ tục.
Ví dụ 1.
Thủ tục LoopImitation(i, n: số nguyên); (Tham số đầu tiên là bộ đếm bước, tham số thứ hai là tổng số bước) started writeln("Hello N", i); // Đây là bất kỳ hướng dẫn nào sẽ được lặp lại nếu tôi Kết quả của lệnh gọi có dạng LoopImitation(1, 10) sẽ là việc thực hiện các lệnh mười lần với bộ đếm thay đổi từ 1 thành 10. Trong trong trường hợp này sẽ được in: Xin chào N1 Nói chung, không khó để thấy rằng các tham số của thủ tục là giới hạn cho việc thay đổi các giá trị của bộ đếm. Bạn có thể hoán đổi lệnh gọi đệ quy và các hướng dẫn được lặp lại, như trong ví dụ sau. Ví dụ 2.
Thủ tục LoopImitation2(i, n: số nguyên); bắt đầu nếu tôi Trong trường hợp này, một lệnh gọi thủ tục đệ quy sẽ xảy ra trước khi các lệnh bắt đầu được thực thi. Trước hết, phiên bản mới của thủ tục cũng sẽ gọi một phiên bản khác, v.v., cho đến khi chúng ta đạt đến giá trị tối đa của bộ đếm. Chỉ sau đó, thủ tục cuối cùng trong số các thủ tục được gọi sẽ thực hiện các lệnh của nó, sau đó thủ tục thứ hai đến cuối cùng sẽ thực hiện các lệnh của nó, v.v. Kết quả của việc gọi LoopImitation2(1, 10) sẽ in lời chào theo thứ tự ngược lại: Xin chào N10 Nếu chúng ta tưởng tượng một chuỗi các thủ tục được gọi đệ quy, thì trong ví dụ 1, chúng ta sẽ thực hiện nó từ các thủ tục được gọi trước đó đến các thủ tục được gọi sau đó. Ở ví dụ 2 thì ngược lại, từ sau đến trước. Cuối cùng, một lệnh gọi đệ quy có thể được đặt giữa hai khối lệnh. Ví dụ: Thủ tục LoopImitation3(i, n: số nguyên); bắt đầu writeln("Xin chào N", i); (Khối hướng dẫn đầu tiên có thể nằm ở đây) nếu tôi Ở đây, các lệnh từ khối đầu tiên được thực hiện tuần tự trước tiên, sau đó các lệnh từ khối thứ hai được thực hiện theo thứ tự ngược lại. Khi gọi LoopImitation3(1, 10), chúng tôi nhận được: Xin chào N1 Sẽ cần hai vòng lặp để thực hiện cùng một việc mà không cần đệ quy. Bạn có thể tận dụng thực tế là việc thực hiện các phần của cùng một quy trình được giãn cách theo thời gian. Ví dụ: Ví dụ 3: Chuyển một số sang nhị phân.
Việc lấy các chữ số của một số nhị phân, như đã biết, xảy ra bằng cách chia số dư cho cơ số của hệ thống số 2. Nếu có một số, thì chữ số cuối cùng của nó trong biểu diễn nhị phân của nó bằng Lấy phần nguyên của phép chia cho 2: chúng ta nhận được một số có cùng biểu diễn nhị phân nhưng không có chữ số cuối cùng. Vì vậy, chỉ cần lặp lại hai thao tác trên là đủ cho đến khi trường chia tiếp theo nhận được phần nguyên bằng 0. Nếu không có đệ quy, nó sẽ trông như thế này: Trong khi x>0 bắt đầu c:=x mod 2; x:=x div 2; viết(c); kết thúc; Vấn đề ở đây là các chữ số của biểu diễn nhị phân được tính theo thứ tự ngược lại (mới nhất trước). Để in một số ở dạng bình thường, bạn sẽ phải nhớ tất cả các số trong các phần tử mảng và in chúng thành một vòng lặp riêng. Sử dụng đệ quy, không khó để đạt được đầu ra theo đúng thứ tự mà không cần mảng và vòng lặp thứ hai. Cụ thể là: Thủ tục Biểu diễn nhị phân(x: số nguyên); var c, x: số nguyên; bắt đầu (Khối đầu tiên. Được thực hiện theo thứ tự gọi thủ tục) c:= x mod 2; x:= x div 2; (Cuộc gọi đệ quy) nếu x>0 thì Biểu diễn nhị phân(x); (Khối thứ hai. Thực hiện theo thứ tự ngược lại) write(c); kết thúc; Nói chung, chúng tôi không nhận được bất kỳ khoản tiền thắng nào. Các chữ số của biểu diễn nhị phân được lưu trữ trong các biến cục bộ, các biến này khác nhau đối với mỗi phiên bản đang chạy của thủ tục đệ quy. Tức là không thể lưu được bộ nhớ. Ngược lại, chúng ta lãng phí thêm bộ nhớ để lưu trữ nhiều biến cục bộ x. Tuy nhiên, giải pháp này có vẻ tốt đẹp đối với tôi. Một dãy các vectơ được cho là có hệ thức truy hồi nếu vectơ ban đầu và sự phụ thuộc hàm của vectơ tiếp theo vào vectơ trước đó được cho trước Một ví dụ đơn giản về đại lượng được tính bằng quan hệ truy hồi là giai thừa Giai thừa tiếp theo có thể được tính từ giai thừa trước đó là: Bằng cách giới thiệu ký hiệu , chúng ta có được mối quan hệ: Các vectơ từ công thức (1) có thể được hiểu là tập hợp các giá trị thay đổi. Sau đó, việc tính toán phần tử cần thiết của chuỗi sẽ bao gồm việc cập nhật lặp lại các giá trị của chúng. Đặc biệt đối với giai thừa: X:= 1; for i:= 2 to n do x:= x * i; viếtln(x); Mỗi bản cập nhật như vậy (x:= x * i) được gọi sự lặp lại và quá trình lặp lại là sự lặp lại. Tuy nhiên, chúng ta hãy lưu ý rằng mối quan hệ (1) là một định nghĩa đệ quy thuần túy của chuỗi và phép tính phần tử thứ n thực sự là việc lấy đi lặp lại hàm f từ chính nó: Đặc biệt, đối với giai thừa người ta có thể viết: Hàm Giai thừa(n: số nguyên): số nguyên; bắt đầu nếu n > 1 thì Giai thừa:= n * Giai thừa(n-1) else Giai thừa:= 1; kết thúc; Cần hiểu rằng việc gọi các hàm đòi hỏi một số chi phí bổ sung, vì vậy tùy chọn đầu tiên để tính giai thừa sẽ nhanh hơn một chút. Nhìn chung, các giải pháp lặp lại hoạt động nhanh hơn các giải pháp đệ quy. Trước khi chuyển sang các tình huống mà đệ quy hữu ích, chúng ta hãy xem thêm một ví dụ về trường hợp nó không nên được sử dụng. Hãy xem xét trương hợp đặc biệt các mối quan hệ lặp lại, khi giá trị tiếp theo trong một chuỗi không phụ thuộc vào một mà phụ thuộc vào một số giá trị trước đó cùng một lúc. Một ví dụ là dãy Fibonacci nổi tiếng, trong đó mỗi chuỗi phần tử tiếp theo là tổng của hai số trước: Với cách tiếp cận “chính diện”, bạn có thể viết: Hàm Fib(n: số nguyên): số nguyên; bắt đầu nếu n > 1 thì Fib:= Fib(n-1) + Fib(n-2) else Fib:= 1; kết thúc; Mỗi lệnh gọi Fib tạo ra hai bản sao của chính nó, mỗi bản sao tạo thêm hai bản sao nữa, v.v. Số lượng hoạt động tăng theo số lượng N theo cấp số nhân, mặc dù đối với một giải pháp lặp tuyến tính trong N số thao tác. Trên thực tế, ví dụ trên dạy chúng ta không KHI không nên sử dụng đệ quy, nếu không LÀM SAO nó không nên được sử dụng. Rốt cuộc, nếu có một giải pháp lặp nhanh (dựa trên vòng lặp), thì vòng lặp tương tự có thể được thực hiện bằng cách sử dụng thủ tục hoặc hàm đệ quy. Ví dụ: // x1, x2 – điều kiện ban đầu(1, 1) // n – số của hàm số Fibonacci được yêu cầu Fib(x1, x2, n: số nguyên): số nguyên; var x3: số nguyên; bắt đầu nếu n > 1 thì bắt đầu x3:= x2 + x1; x1:= x2; x2:= x3; Fib:= Fib(x1, x2, n-1); end else Fib:= x2; kết thúc; Tuy nhiên, các giải pháp lặp đi lặp lại vẫn được ưa chuộng hơn. Câu hỏi đặt ra là khi nào trong trường hợp này bạn nên sử dụng đệ quy? Bất kì thủ tục đệ quy và các hàm chỉ chứa một lệnh gọi đệ quy đến chính chúng có thể dễ dàng được thay thế bằng các vòng lặp. Để có được thứ gì đó không có bản sao đơn giản không đệ quy, bạn cần sử dụng các thủ tục và hàm tự gọi chúng hai lần trở lên. Trong trường hợp này, tập hợp các thủ tục được gọi không còn tạo thành một chuỗi nữa, như trong Hình 2. 1 mà là cả một cái cây. Có rất nhiều loại vấn đề khi quá trình tính toán phải được tổ chức theo cách này. Đối với họ, đệ quy sẽ là giải pháp đơn giản và tự nhiên nhất. Cơ sở lý thuyết cho các hàm đệ quy gọi chính chúng nhiều lần là nhánh của toán học rời rạc nghiên cứu về cây. Sự định nghĩa:
chúng ta sẽ gọi tập hợp hữu hạn T, bao gồm một hoặc nhiều nút sao cho: Định nghĩa này là đệ quy. Nói tóm lại, cây là một tập hợp bao gồm một gốc và các cây con gắn liền với nó, cũng là cây. Một cái cây được xác định thông qua chính nó. Tuy nhiên định nghĩa này có ý nghĩa, vì đệ quy là hữu hạn. Mỗi cây con chứa ít nút hơn cây chứa nó. Cuối cùng, chúng ta đến với các cây con chỉ chứa một nút và điều này đã rõ nó là gì. Cơm. 3. Cây. Trong bộ lễ phục. Hình 3 cho thấy một cây có bảy nút. Mặc dù những cây bình thường mọc từ dưới lên trên nhưng người ta thường vẽ chúng theo cách khác. Khi vẽ sơ đồ bằng tay, phương pháp này rõ ràng thuận tiện hơn. Vì sự không nhất quán này, đôi khi nảy sinh sự nhầm lẫn khi một nút được cho là ở trên hoặc dưới nút khác. Vì lý do này, sẽ thuận tiện hơn khi sử dụng thuật ngữ được sử dụng khi mô tả cây phả hệ, gọi các nút gần tổ tiên gốc hơn và các nút ở xa hơn là con cháu. Một cái cây có thể được mô tả bằng đồ họa theo một số cách khác. Một số trong số chúng được hiển thị trong hình. 4. Theo định nghĩa, cây là một hệ thống các tập hợp lồng nhau, trong đó các tập hợp này không giao nhau hoặc hoàn toàn chứa trong nhau. Các tập hợp như vậy có thể được mô tả dưới dạng các vùng trên mặt phẳng (Hình 4a). Trong bộ lễ phục. 4b, các tập hợp lồng nhau không nằm trên một mặt phẳng mà được kéo dài thành một đường thẳng. Cơm. 4b cũng có thể được xem như sơ đồ của một số công thức đại số có chứa dấu ngoặc đơn lồng nhau. Cơm. Hình 4c đưa ra một cách phổ biến khác để biểu diễn cấu trúc cây dưới dạng danh sách so le. Cơm. 4. Các cách khác để biểu diễn cấu trúc cây: (a) các tập hợp lồng nhau; (b) dấu ngoặc đơn lồng nhau; (c) danh sách nhượng quyền. Danh sách so le có những điểm tương đồng rõ ràng với phương pháp định dạng Mã chương trình. Thật vậy, một chương trình được viết trong mô hình lập trình có cấu trúc, có thể được biểu diễn dưới dạng cây bao gồm các cấu trúc lồng vào nhau. Bạn cũng có thể vẽ ra sự tương tự giữa danh sách gờ và vẻ bề ngoài bảng mục lục trong sách có các phần chứa các phần phụ, các phần này lần lượt chứa các phần phụ, v.v. Cách đánh số truyền thống các phần như vậy (phần 1, tiểu mục 1.1 và 1.2, tiểu mục 1.1.2, v.v.) được gọi là hệ thập phân Dewey. Áp dụng cho cây trong hình. 3 và 4 hệ thống này sẽ cung cấp: 1. A; 1,1B; 1,2 C; 1.2.1D; 1.2.2 E; 1.2.3 F; 1.2.3.1G; Trong tất cả các thuật toán liên quan đến cấu trúc cây, luôn xuất hiện cùng một ý tưởng, đó là ý tưởng đi qua hoặc duyệt cây. Đây là cách truy cập các nút cây trong đó mỗi nút được duyệt chính xác một lần. Điều này dẫn đến sự sắp xếp tuyến tính của các nút cây. Đặc biệt, có ba cách: bạn có thể đi qua các nút theo thứ tự tiến, lùi và kết thúc. Thuật toán truyền tải tiếp theo: Thuật toán này là đệ quy, vì việc duyệt cây bao gồm việc duyệt các cây con và chúng lần lượt được duyệt bằng cùng một thuật toán. Đặc biệt, đối với cây trong hình. 3 và 4, truyền tải trực tiếp cho một chuỗi các nút: A, B, C, D, E, F, G. Chuỗi kết quả tương ứng với việc liệt kê các nút từ trái sang phải tuần tự khi biểu diễn một cây bằng cách sử dụng dấu ngoặc đơn lồng nhau và trong hệ thống thập phân Dewey, cũng như đoạn văn từ trên xuống khi được trình bày dưới dạng danh sách bậc thang. Khi triển khai thuật toán này trong ngôn ngữ lập trình, việc truy cập vào gốc tương ứng với thủ tục hoặc hàm thực hiện một số hành động và việc đi qua các cây con tương ứng với các lệnh gọi đệ quy đến chính nó. Cụ thể, đối với cây nhị phân (trong đó mỗi nút có nhiều nhất hai cây con), quy trình tương ứng sẽ như sau: // Preorder Traversal – Tên tiếng Anh của thủ tục đặt hàng trực tiếp PreorderTraversal((Arguments)); bắt đầu //Truyền gốc DoS Something((Đối số)); //Chuyển đổi cây con bên trái if (Có một cây con bên trái) then PreorderTransversal((Đối số 2)); //Chuyển cây con bên phải if (Có cây con bên phải) then PreorderTransversal((Đối số 3)); kết thúc; Nghĩa là, đầu tiên thủ tục thực hiện tất cả các hành động và chỉ sau đó tất cả các lệnh gọi đệ quy mới xảy ra. Thuật toán truyền tải ngược: Nghĩa là, tất cả các cây con đều được duyệt từ trái sang phải và đường trở về gốc nằm giữa các lần duyệt này. Đối với cây trong hình. 3 và 4 điều này đưa ra chuỗi các nút: B, A, D, C, E, G, F. Trong thủ tục đệ quy tương ứng, các hành động sẽ được đặt trong khoảng trống giữa các lệnh gọi đệ quy. Cụ thể cho cây nhị phân: // Inorder Traversal – Tên tiếng Anh của thủ tục đảo ngược InorderTraversal((Arguments)); bắt đầu //Di chuyển cây con bên trái if (Có một cây con bên trái) sau đó InorderTraversal((Đối số 2)); //Truyền gốc DoS Something((Đối số)); // Duyệt cây con bên phải nếu (Có một cây con bên phải) rồi InorderTraversal((Đối số 3)); kết thúc; Thuật toán duyệt theo thứ tự cuối: Đối với cây trong hình. 3 và 4 điều này sẽ đưa ra chuỗi các nút: B, D, E, G, F, C, A. Trong thủ tục đệ quy tương ứng, các hành động sẽ được đặt sau lệnh gọi đệ quy. Cụ thể cho cây nhị phân: // Postorder Traversal – Tên tiếng Anh của thủ tục đặt hàng cuối cùng PostorderTraversal((Arguments)); bắt đầu //Di chuyển cây con bên trái if (Có một cây con bên trái) then PostorderTraversal((Đối số 2)); // Vượt cây con bên phải if (Có cây con bên phải) rồi PostorderTraversal((Đối số 3)); //Truyền gốc DoS Something((Đối số)); kết thúc; Nếu một số thông tin nằm trong các nút cây thì bạn có thể sử dụng tương ứng cấu trúc động dữ liệu. Trong Pascal việc này được thực hiện bằng cách sử dụng loại biến một bản ghi chứa các con trỏ tới các cây con cùng loại. Ví dụ: một cây nhị phân trong đó mỗi nút chứa một số nguyên có thể được lưu trữ bằng biến loại PTree, được mô tả dưới đây: Gõ PTree = ^TTree; TTree = bản ghi Inf: số nguyên; LeftSubTree, RightSubTree: PTree; kết thúc; Mỗi nút có một loại PTree. Đây là một con trỏ, nghĩa là mỗi nút phải được tạo bằng cách gọi thủ tục Mới trên đó. Nếu nút là nút lá thì các trường LeftSubTree và RightSubTree của nó được gán giá trị không. Mặt khác, các nút LeftSubTree và RightSubTree cũng được tạo bằng quy trình Mới. Một bản ghi như vậy được hiển thị dưới dạng sơ đồ trong Hình. 5. Cơm. 5. Sơ đồ biểu diễn bản ghi loại TTree. Bản ghi có ba trường: Inf – một số, LeftSubTree và RightSubTree – con trỏ tới các bản ghi cùng loại TTree. Một ví dụ về cây được tạo thành từ các bản ghi như vậy được hiển thị trong Hình 6. Cơm. 6. Một cây được tạo thành từ các bản ghi loại TTree. Mỗi mục lưu trữ một số và hai con trỏ có thể chứa một trong hai không hoặc địa chỉ của các bản ghi khác cùng loại. Nếu trước đây bạn chưa từng làm việc với các cấu trúc bao gồm các bản ghi chứa các liên kết đến các bản ghi cùng loại, chúng tôi khuyên bạn nên tự làm quen với tài liệu về nó. Hãy xem xét thuật toán vẽ cây như trong Hình. 6. Nếu mỗi dòng được coi là một nút thì bức ảnh này thỏa mãn đầy đủ định nghĩa về cây ở phần trước. Cơm. 6. Cây. Thủ tục đệ quy rõ ràng sẽ vẽ một đường (thân cây lên đến nhánh đầu tiên), sau đó gọi chính nó để vẽ hai cây con. Cây con khác với cây chứa chúng ở tọa độ điểm bắt đầu, góc quay, chiều dài thân và số nhánh mà chúng chứa (ít hơn một). Tất cả những khác biệt này phải được coi là tham số của thủ tục đệ quy. Một ví dụ về quy trình như vậy, được viết bằng Delphi, được trình bày dưới đây: Cây thủ tục(Canvas: TCanvas; // Canvas trên đó cây sẽ được vẽ x,y: mở rộng; // Tọa độ gốc Góc: mở rộng; // Góc mà cây mọc Chiều dài thân cây: mở rộng; // Chiều dài thân cây n: số nguyên // Số nhánh (còn bao nhiêu // lệnh gọi đệ quy chưa được thực hiện)); var x2, y2: mở rộng; // Điểm cuối thân cây (điểm nhánh) bắt đầu x2:= x + Chiều dài thân cây * cos(Góc); y2:= y - Chiều dài thân cây * sin(Góc); Canvas.MoveTo(round(x), round(y)); Canvas.LineTo(round(x2), round(y2)); nếu n > 1 thì bắt đầu Cây(Canvas, x2, y2, Angle+Pi/4, 0,55*TrunkLength, n-1); Cây(Canvas, x2, y2, Angle-Pi/4, 0,55*Chiều dài thân cây, n-1); kết thúc; kết thúc; Để có được Hình. 6 thủ tục này được gọi với các tham số sau: Cây(Image1.Canvas, 175, 325, Pi/2, 120, 15); Lưu ý rằng việc vẽ được thực hiện trước các lệnh gọi đệ quy, nghĩa là cây được vẽ theo thứ tự trực tiếp. Theo truyền thuyết ở Đại chùa Banaras, dưới thánh đường đánh dấu giữa thế giới có một chiếc đĩa đồng trên đó cố định 3 thanh kim cương, cao một cubit và dày như con ong. Cách đây rất lâu, ngay từ thuở sơ khai, các tu sĩ của tu viện này đã phạm tội trước thần Brahma. Tức giận, Brahma dựng ba cây gậy cao và đặt 64 chiếc đĩa vàng ròng lên một chiếc, sao cho mỗi chiếc đĩa nhỏ hơn nằm trên một chiếc lớn hơn. Ngay khi tất cả 64 chiếc đĩa được chuyển từ cây gậy mà Thần Brahma đã đặt chúng khi tạo ra thế giới sang một cây gậy khác, tòa tháp cùng với ngôi đền sẽ biến thành cát bụi và thế giới sẽ bị diệt vong dưới những tiếng sấm sét. Độc lập với Brahma, câu đố này được nhà toán học người Pháp Edouard Lucas đề xuất vào cuối thế kỷ 19. Phiên bản bán ra thường dùng 7-8 đĩa (Hình 7). Cơm. 7. Câu đố “Tháp Hà Nội”. Giả sử rằng có một giải pháp cho N-1 đĩa. Sau đó để chuyển Nđĩa, tiến hành như sau: 1) Thay đổi N-1 đĩa. Vì đối với trường hợp N= 1 là thuật toán sắp xếp lại hiển nhiên, khi đó bằng quy nạp, sử dụng các thao tác (1) – (3), ta có thể sắp xếp lại số đĩa tùy ý. Hãy tạo một quy trình đệ quy in toàn bộ chuỗi các ca làm việc cho một số đĩa nhất định. Mỗi lần thủ tục như vậy được gọi, nó phải in thông tin về một ca (từ điểm 2 của thuật toán). Đối với việc sắp xếp lại từ điểm (1) và (3), quy trình sẽ tự gọi với số lượng đĩa giảm đi một. //n – số lượng đĩa // a, b, c – số pin. Việc dịch chuyển được thực hiện từ chân a, // sang chân b bằng chân phụ c. thủ tục Hà Nội(n, a, b, c: số nguyên); bắt đầu nếu n > 1 thì bắt đầu Hà Nội(n-1, a, c, b); writeln(a, " -> ", b); Hà Nội(n-1,c,b,a); end else writeln(a, " -> ", b); kết thúc; Lưu ý rằng tập hợp các thủ tục được gọi đệ quy trong trường hợp này tạo thành một cây duyệt theo thứ tự ngược lại. Nhiệm vụ phân tích cú pháp là tính giá trị của biểu thức bằng cách sử dụng một dòng hiện có chứa biểu thức số học và các giá trị đã biết của các biến có trong nó. Quá trình tính toán các biểu thức số học có thể được biểu diễn dưới dạng cây nhị phân. Thật vậy, mỗi toán tử số học (+, –, *, /) yêu cầu hai toán hạng, cũng sẽ là các biểu thức số học và do đó, có thể được coi là cây con. Cơm. Hình 8 cho thấy một ví dụ về cây tương ứng với biểu thức: Cơm. 8. Cây cú pháp tương ứng với biểu thức số học (6). Trong cây như vậy, các nút cuối sẽ luôn là các biến (ở đây x) hoặc các hằng số và tất cả các nút bên trong sẽ chứa các toán tử số học. Để thực thi một toán tử, trước tiên bạn phải đánh giá các toán hạng của nó. Vì vậy, cây trong hình phải được duyệt theo thứ tự cuối cùng. Trình tự tương ứng của các nút gọi điện đảo ngược ký hiệu tiếng Ba Lan
biểu thức số học. Khi xây dựng cây cú pháp, bạn nên chú ý đến tính năng tiếp theo. Ví dụ, nếu có một biểu thức và chúng ta sẽ đọc các phép tính cộng, trừ từ trái sang phải, khi đó cây cú pháp đúng sẽ chứa dấu trừ thay vì dấu cộng (Hình 9a). Về bản chất, cây này tương ứng với biểu thức Có thể tạo cây dễ dàng hơn nếu bạn phân tích biểu thức (8) ngược lại, từ phải sang trái. Trong trường hợp này, kết quả là một cây có hình. 9b tương đương với cây 8a nhưng không yêu cầu thay dấu. Tương tự, từ phải sang trái, bạn cần phân tích các biểu thức chứa toán tử nhân và chia. Cơm. 9. Cây cú pháp biểu thức Một – b + c khi đọc từ trái sang phải (a) và từ phải sang trái (b). Cách tiếp cận này không loại bỏ hoàn toàn sự đệ quy. Tuy nhiên, nó cho phép bạn giới hạn bản thân chỉ một lần gọi thủ tục đệ quy, điều này có thể đủ nếu động cơ là tối đa hóa hiệu suất. Ý tưởng cách tiếp cận này là thay thế các cuộc gọi đệ quy bằng một vòng lặp đơn giản sẽ được thực hiện nhiều lần tùy theo số nút trong cây được hình thành bởi các thủ tục đệ quy. Chính xác những gì sẽ được thực hiện ở mỗi bước phải được xác định bằng số bước. So sánh số bước và các hành động cần thiết không phải là một nhiệm vụ tầm thường và trong mỗi trường hợp, nó sẽ phải được giải quyết riêng biệt. Ví dụ: giả sử bạn muốn làm k vòng lồng nhau N các bước trong mỗi: Đối với i1:= 0 đến n-1 làm cho i2:= 0 đến n-1 làm cho i3:= 0 đến n-1 làm … Nếu như k không được biết trước nên không thể viết chúng một cách rõ ràng như đã trình bày ở trên. Sử dụng kỹ thuật được trình bày trong Phần 6.5, bạn có thể đạt được số vòng lặp lồng nhau cần thiết bằng cách sử dụng quy trình đệ quy: Thủ tục NestedCycles(Chỉ mục: mảng số nguyên; n, k, độ sâu: số nguyên); var i: số nguyên; bắt đầu nếu độ sâu Để loại bỏ đệ quy và rút gọn mọi thứ thành một chu trình, hãy lưu ý rằng nếu bạn đánh số các bước trong hệ thống số cơ số N, khi đó mỗi bước có một số gồm các số i1, i2, i3,... hoặc các giá trị tương ứng từ mảng Indexes. Nghĩa là, các số tương ứng với giá trị của bộ đếm chu kỳ. Số bước trong ký hiệu thập phân thông thường: Sẽ có tổng cộng các bước n k. Bằng cách duyệt qua các số của chúng trong hệ thống số thập phân và chuyển đổi từng số đó sang hệ cơ số N, chúng tôi nhận được các giá trị chỉ mục: M:= round(IntPower(n, k)); đối với i:= 0 đến M-1 bắt đầu Number:= i; đối với p:= 0 đến k-1 hãy bắt đầu Chỉ mục := Number mod n; Số:= Số div n; kết thúc; DoSomething(Chỉ mục); kết thúc; Chúng tôi xin lưu ý một lần nữa rằng phương pháp này không phổ biến và bạn sẽ phải nghĩ ra phương pháp nào đó khác nhau cho mỗi nhiệm vụ. 1. Xác định xem các thủ tục và hàm đệ quy sau đây sẽ làm gì. (a) Thủ tục sau sẽ in ra kết quả gì khi Rec(4) được gọi? Thủ tục Rec(a: số nguyên); bắt đầu viết(a); nếu a>0 thì Rec(a-1); viếtln(a); kết thúc; (b) Giá trị của hàm Nod(78, 26) sẽ là bao nhiêu? Hàm Nod(a, b: số nguyên): số nguyên; bắt đầu nếu a > b thì Nod:= Nod(a – b, b) else if b > a then Nod:= Nod(a, b – a) else Nod:= a; kết thúc; (c) Những gì sẽ được in ra bởi các thủ tục dưới đây khi A(1) được gọi? Thủ tục A(n: số nguyên); thủ tục B(n: số nguyên); thủ tục A(n: số nguyên); bắt đầu viết(n); B(n-1); kết thúc; thủ tục B(n: số nguyên); bắt đầu viết(n); nếu n (d) Thủ tục dưới đây sẽ in ra kết quả gì khi gọi BT(0, 1, 3)? Thủ tục BT(x: số thực; D, MaxD: số nguyên); bắt đầu nếu D = MaxD thì writeln(x) ngược lại bắt đầu BT(x – 1, D + 1, MaxD); BT(x+1, D+1, MaxD); kết thúc; kết thúc; 2. Ouroboros - con rắn tự nuốt chửng cái đuôi của mình (Hình 14) khi xòe ra có chiều dài L, đường kính quanh đầu D, độ dày thành bụng d. Xác định xem anh ta có thể nhét bao nhiêu cái đuôi vào mình và sau đó cái đuôi sẽ được xếp vào bao nhiêu lớp? Cơm. 14. Ouroboros mở rộng. 3. Đối với cây trong hình. 10a chỉ ra trình tự truy cập các nút theo thứ tự truyền tải tiến, lùi và kết thúc. 4. Mô tả đồ họa cây được xác định bằng các dấu ngoặc lồng nhau: (A(B(C, D), E), F, G). 5. Mô tả bằng đồ họa cây cú pháp của biểu thức số học sau: Viết biểu thức này bằng ký hiệu Ba Lan ngược. 6. Đối với biểu đồ bên dưới (Hình 15), hãy viết ma trận kề và ma trận tỷ lệ. 1. Đã tính đủ giai thừa một số lượng lớn lần (một triệu hoặc nhiều hơn), so sánh tính hiệu quả của các thuật toán đệ quy và lặp lại. Thời gian thực hiện sẽ khác nhau bao nhiêu lần và tỷ lệ này sẽ phụ thuộc như thế nào vào số có giai thừa đang được tính? 2. Viết hàm đệ quy để kiểm tra xem dấu ngoặc đơn có được đặt đúng trong chuỗi hay không. Nếu sự sắp xếp đúng thì thỏa mãn các điều kiện sau: (a) số dấu ngoặc đơn mở và đóng bằng nhau. Ví dụ về vị trí không chính xác:)(, ())(, ())((), v.v. 3. Dòng này có thể chứa cả dấu ngoặc tròn và dấu ngoặc vuông. Mỗi dấu ngoặc đơn mở có một dấu ngoặc đơn đóng tương ứng cùng loại (round - round, vuông - vuông). Viết hàm đệ quy để kiểm tra xem dấu ngoặc đơn có được đặt đúng trong trường hợp này hay không. Ví dụ về vị trí không chính xác: ([)]. 4. Số cấu trúc ngoặc thông thường có độ dài 6 là 5: ()()(), (())(), ()(()), ((())), (()()). Ghi chú: Cấu trúc dấu ngoặc đơn đúng có độ dài tối thiểu "()". Cấu trúc có chiều dài dài hơn thu được từ cấu trúc có chiều dài ngắn hơn theo hai cách: (a) nếu cấu trúc nhỏ hơn được đưa vào ngoặc, 5. Tạo một thủ tục in ra tất cả các hoán vị có thể có của các số nguyên từ 1 đến N. 6. Tạo thủ tục in tất cả các tập hợp con của tập hợp (1, 2, ..., N). 7. Tạo quy trình in tất cả các chế độ xem có thể số tự nhiên N là tổng của các số tự nhiên khác. 8. Tạo hàm tính tổng các phần tử mảng bằng cách đến thuật toán sau: Mảng được chia đôi, tổng các phần tử trong mỗi nửa được tính và cộng lại. Tổng của các phần tử trong một nửa mảng được tính bằng cùng một thuật toán, nghĩa là một lần nữa bằng cách chia đôi. Việc phân chia diễn ra cho đến khi các phần kết quả của mảng chứa mỗi phần tử một phần tử và việc tính tổng theo đó trở nên tầm thường. Bình luận: Thuật toán này là một giải pháp thay thế. Trong trường hợp mảng có giá trị thực, nó thường cho phép sai số làm tròn nhỏ hơn. 10. Tạo quy trình vẽ đường cong Koch (Hình 12). 11. Tái tạo hình. 16. Trong hình, ở mỗi lần lặp tiếp theo, vòng tròn nhỏ hơn 2,5 lần (hệ số này có thể được coi là tham số). 1. D. Knuth. Nghệ thuật lập trình máy tính. câu 1. (phần 2.3. “Cây cối”). Xin chào Habrahabr! Trong bài viết này chúng ta sẽ nói về các vấn đề đệ quy và cách giải quyết chúng. Trong lập trình, đệ quy có quan hệ mật thiết với hàm; chính xác hơn là nhờ hàm trong lập trình mà mới có thứ gọi là đệ quy hay hàm đệ quy. Nói một cách đơn giản, đệ quy là định nghĩa một phần của hàm (phương thức) thông qua chính nó, tức là nó là hàm gọi chính nó, trực tiếp (trong thân hàm) hoặc gián tiếp (thông qua hàm khác). Rất nhiều điều đã được nói về sự đệ quy. Dưới đây là một số tài nguyên tốt: từ mạng Bất kỳ thuật toán nào được thực hiện ở dạng đệ quy đều có thể được viết lại ở dạng lặp và ngược lại. Câu hỏi đặt ra là liệu điều này có cần thiết hay không và nó sẽ hiệu quả đến mức nào. Để biện minh cho điều này, các lập luận sau đây có thể được đưa ra. Để bắt đầu, chúng ta có thể nhớ lại các định nghĩa về đệ quy và lặp lại. Đệ quy là một cách tổ chức xử lý dữ liệu trong đó chương trình gọi chính nó trực tiếp hoặc với sự trợ giúp của các chương trình khác. Lặp lại là một cách tổ chức xử lý dữ liệu trong đó hành động nhất địnhđược lặp đi lặp lại nhiều lần mà không dẫn đến việc gọi chương trình đệ quy. Sau đó, chúng ta có thể kết luận rằng chúng có thể thay thế cho nhau, nhưng không phải lúc nào cũng có cùng chi phí về tài nguyên và tốc độ. Để chứng minh điều này, chúng ta có thể đưa ra ví dụ sau: có một hàm trong đó để tổ chức một thuật toán nhất định, có một vòng lặp thực hiện một chuỗi hành động tùy thuộc vào giá trị hiện tại của bộ đếm (nó có thể không phụ thuộc vào Nó). Vì có một chu trình, có nghĩa là cơ thể lặp lại một chuỗi hành động - sự lặp lại của chu trình. Bạn có thể di chuyển các thao tác vào một chương trình con riêng biệt và chuyển cho nó giá trị bộ đếm, nếu có. Sau khi hoàn thành việc thực thi chương trình con, chúng tôi kiểm tra các điều kiện để thực hiện vòng lặp và nếu nó đúng, chúng tôi tiến hành gọi chương trình con mới; nếu nó sai, chúng tôi hoàn thành việc thực thi. Bởi vì Chúng ta đặt tất cả nội dung của vòng lặp vào một chương trình con, nghĩa là điều kiện để thực hiện vòng lặp cũng được đặt trong chương trình con và có thể lấy được thông qua giá trị trả về của hàm, các tham số được truyền bằng tham chiếu hoặc con trỏ tới chương trình con , cũng như các biến toàn cục. Hơn nữa, thật dễ dàng để chỉ ra rằng một lệnh gọi đến một chương trình con nhất định từ một vòng lặp có thể dễ dàng được chuyển đổi thành lệnh gọi hoặc không gọi (trả về một giá trị hoặc đơn giản là hoàn thành công việc) của một chương trình con từ chính nó, được hướng dẫn bởi một số điều kiện (những điều kiện mà trước đây ở trạng thái vòng lặp). Bây giờ nếu bạn nhìn vào chương trình trừu tượng, nó gần giống như chuyển các giá trị cho một chương trình con và sử dụng chúng, chương trình con này sẽ thay đổi sau khi hoàn thành, tức là. chúng tôi đã thay thế vòng lặp bằng lệnh gọi đệ quy đến một chương trình con để giải một thuật toán nhất định. Nhiệm vụ đưa đệ quy vào một cách tiếp cận lặp lại là có tính đối xứng. Tóm lại, chúng ta có thể bày tỏ những suy nghĩ sau: đối với mỗi cách tiếp cận, có một loại nhiệm vụ riêng, được xác định bởi các yêu cầu cụ thể cho một nhiệm vụ cụ thể. Bạn có thể tìm hiểu thêm về điều này Vì vậy hàm đệ quy bao gồm Giải pháp lớp công khai ( public static int recursion(int n) ( // thoát điều kiện // Trường hợp cơ sở // khi nào dừng lặp lại đệ quy? if (n == 1) ( return 1; ) // Bước đệ quy / trả về điều kiện đệ quy đệ quy( n - 1) * n; ) public static void main(String args) ( System.out.println(recursion(5)); // gọi hàm đệ quy ) ) Ở đây điều kiện cơ bản là điều kiện khi n=1. Vì chúng ta biết rằng 1!=1 và để tính 1! chúng tôi không cần bất cứ điều gì Để tính 2! chúng ta có thể sử dụng 1!, tức là 2!=1!*2. Để tính 3! chúng ta cần 2!*3... Để tính n! chúng ta cần (n-1)!*n. Đây là bước đệ quy. Nói cách khác, để lấy giá trị giai thừa của một số n, chỉ cần nhân giá trị giai thừa của số trước đó với n là đủ. Thẻ: Thêm thẻ Đệ quy là một hiện tượng khá phổ biến xảy ra không chỉ trong lĩnh vực khoa học mà còn trong đời sống hàng ngày. Ví dụ: hiệu ứng Droste, tam giác Sierpinski, v.v. Cách dễ nhất để xem đệ quy là hướng camera Web vào màn hình điều khiển máy tính, một cách tự nhiên, sau khi bật nó lên. Như vậy, camera sẽ ghi lại hình ảnh của màn hình máy tính và hiển thị lên màn hình này, nó sẽ giống như một vòng khép kín. Kết quả là chúng ta sẽ quan sát thấy thứ gì đó tương tự như một đường hầm. Trong lập trình, đệ quy có quan hệ mật thiết với các hàm; chính xác hơn là nhờ các hàm trong lập trình mà mới có thứ gọi là đệ quy hay hàm đệ quy. Nói một cách đơn giản, đệ quy là định nghĩa một phần của hàm (phương thức) thông qua chính nó, tức là nó là hàm gọi chính nó, trực tiếp (trong thân hàm) hoặc gián tiếp (thông qua một hàm khác). Các bài toán đệ quy điển hình là: tìm số n!, Fibonacci. Chúng tôi đã giải quyết những vấn đề như vậy, nhưng sử dụng các vòng lặp, nghĩa là lặp đi lặp lại. Nói chung, mọi thứ được giải lặp lại đều có thể được giải bằng đệ quy, nghĩa là sử dụng hàm đệ quy. Toàn bộ giải pháp bắt nguồn từ việc giải quyết trường hợp chính hoặc, như nó còn được gọi là trường hợp cơ sở. Có một thứ gọi là bước đệ quy hoặc lệnh gọi đệ quy. Trong trường hợp hàm đệ quy được gọi để giải quyết một vấn đề phức tạp (không phải trường hợp cơ bản), một số lệnh gọi hoặc bước đệ quy được thực hiện để giảm vấn đề xuống đơn giản hơn. Và cứ như vậy cho đến khi chúng ta có được lời giải cơ bản. Hãy phát triển một chương trình khai báo hàm đệ quy tính n! "stdafx.h" #include // mã Code::Khối // Mã Dev-C++ // giai thừa.cpp: Xác định điểm vào cho ứng dụng bảng điều khiển. #bao gồm TRONG dòng 7, 9, 21 Kiểu dữ liệu được khai báo unsigned long int , vì giá trị của giai thừa tăng rất nhanh, chẳng hạn đã là 10! = 3.628.800. Nếu kích thước của kiểu dữ liệu không đủ thì kết quả là chúng ta sẽ nhận được một giá trị hoàn toàn không chính xác. Mã khai báo nhiều toán tử hơn mức cần thiết để tìm n!. Điều này được thực hiện để sau khi chạy, chương trình sẽ hiển thị những gì xảy ra ở mỗi bước của lệnh gọi đệ quy. Xin lưu ý các dòng mã được đánh dấu, dòng 23, 24, 28 là một giải pháp đệ quy cho n!. Dòng 23, 24 là nghiệm cơ bản của hàm đệ quy, nghĩa là ngay khi giá trị của biến f sẽ bằng 1 hoặc 0 (vì chúng ta biết rằng 1! = 1 và 0! = 1), các lệnh gọi đệ quy sẽ dừng và các giá trị sẽ bắt đầu được trả về cho mỗi lệnh gọi đệ quy. Khi giá trị của lệnh gọi đệ quy đầu tiên trả về, chương trình sẽ trả về giá trị của giai thừa đã tính. TRONG dòng 28 hàm giai thừa() gọi chính nó, nhưng đối số của nó ít hơn một. Đối số được giảm bớt mỗi lần để đạt được một giải pháp cụ thể. Kết quả của chương trình (xem Hình 1). Nhập n!: 5 Bước 1 Kết quả= 0 Bước 2 Kết quả= 0 Bước 3 Kết quả= 0 Bước 4 Kết quả= 0 5!=120 Hình 1 - Đệ quy trong C++ Dựa trên kết quả của chương trình, mỗi bước được hiển thị rõ ràng và kết quả ở mỗi bước bằng 0, ngoại trừ lệnh gọi đệ quy cuối cùng. Cần phải tính năm giai thừa. Chương trình đã thực hiện bốn lệnh gọi đệ quy và ở lệnh gọi thứ năm, trường hợp cơ bản đã được tìm thấy. Và khi chương trình đã có lời giải cho trường hợp cơ bản, nó sẽ giải quyết các bước trước đó và đưa ra kết quả tổng thể. Trong Hình 1, chỉ có bốn bước được hiển thị vì ở bước thứ năm, một giải pháp một phần đã được tìm thấy, giải pháp cuối cùng trả về giải pháp cuối cùng, tức là 120. Hình 2 hiển thị sơ đồ tính toán đệ quy 5!. Sơ đồ cho thấy rõ ràng rằng kết quả đầu tiên được trả về khi đạt được một giải pháp cụ thể, nhưng không phải ngay lập tức, sau mỗi lệnh gọi đệ quy. Hình 2 - Đệ quy trong C++ Vậy tìm được 5! cần biết 4! và nhân nó với 5; 4! = 4 * 3! và như thế. Theo sơ đồ trong Hình 2, phép tính sẽ được rút gọn thành việc tìm một trường hợp đặc biệt, tức là 1!, sau đó các giá trị sẽ lần lượt được trả về cho từng lệnh gọi đệ quy. Cuộc gọi đệ quy cuối cùng sẽ trả về giá trị 5!. Chúng ta hãy làm lại chương trình tìm giai thừa để có được bảng giai thừa. Để làm điều này, chúng ta sẽ khai báo một vòng lặp for trong đó chúng ta sẽ gọi hàm đệ quy. // mã Code::Khối // Mã Dev-C++ // fibonacci.cpp: xác định điểm vào cho ứng dụng console. #bao gồm // mã Code::Khối // Mã Dev-C++ // hanoi_tower.cpp: Xác định điểm vào cho ứng dụng console. // Chương trình giải đệ quy bài toán Tháp Hà Nội #include Hình 5 thể hiện một ví dụ về chương trình đệ quy Tháp Hà Nội. Đầu tiên, chúng tôi nhập số đĩa bằng ba, sau đó chúng tôi nhập thanh cơ sở (đầu tiên) và chỉ định thanh cuối cùng (thứ ba). Tự động thanh thứ hai trở thành thanh phụ. Chương trình tạo ra kết quả hoàn toàn trùng khớp với giải pháp hoạt hình cho vấn đề này. Nhập số đĩa: 3 Nhập số thanh cơ bản: 1 Nhập số thanh cuối cùng: 3 1) 1 -> 3 2) 1 -> 2 3) 3 -> 2 4) 1 -> 3 5) 2 -> 1 6) 2 -> 3 7) 1 -> 3 Hình 5 - Đệ quy trong C++ Từ hình vẽ có thể thấy rằng đầu tiên đĩa di chuyển từ thanh 1 sang thanh 3, sau đó từ thanh 1 sang thanh 2, từ thanh 3 sang thanh 3.hai, v.v. Nghĩa là, chương trình chỉ hiển thị trình tự chuyển động của đĩa và số bước tối thiểu mà tất cả các đĩa sẽ được di chuyển. Tất cả những vấn đề này có thể được giải quyết lặp đi lặp lại. Câu hỏi được đặt ra: “Cái nào tốt hơn để giải quyết, lặp đi lặp lại hay đệ quy?” Tôi trả lời: “Nhược điểm của đệ quy là nó tiêu tốn nhiều tài nguyên máy tính hơn so với phép lặp. Điều này dẫn đến tải nặng cho cả RAM và bộ xử lý. Nếu rõ ràng là một vấn đề cụ thể có thể được giải theo cách lặp đi lặp lại thì nó nên được sử dụng theo cách khác, sử dụng đệ quy!” Tùy thuộc vào vấn đề đang được giải quyết, độ phức tạp của việc viết chương trình sẽ thay đổi khi sử dụng phương pháp giải này hoặc phương pháp giải khác. Nhưng thường xuyên hơn, một vấn đề được giải quyết bằng phương pháp đệ quy xét theo quan điểm khả năng đọc mã sẽ rõ ràng và ngắn gọn hơn nhiều. Để không phải viết một bài báo dài, trong đó sẽ có rất nhiều ví dụ về đệ quy trong C++, tôi sẽ viết thêm một ví dụ về đệ quy ở đây. Nhìn chung, những người hiểu những điều cơ bản và cách sử dụng đệ quy trực tiếp trong các hàm của mình có thể bỏ qua tài liệu này. Đây là một ví dụ về cách sử dụng đệ quy, như trong bài viết Hàm trong C++ dành cho người mới bắt đầu. đệ quy Bài 1 – Sử dụng đệ quy, hiển thị giai thừa của một số từ 1 đến N #bao gồm #bao gồm #bao gồm int chính() getch(); Một chương trình trống đã được tạo, tôi nghĩ không cần bình luận #bao gồm #bao gồm #bao gồm //Hàm đệ quy của chúng ta //0! = 1, 1!=1, 2!=2, 3!=6... Bởi vì 2 số đầu tiên là số 1 và không theo thứ tự nghiêm ngặt, chúng tôi buộc điểm này trong mã nếu n<2
return 1
;
int chính() Phần chính trong chương trình đệ quy C++ Hàm của chúng tôi tính toán lại để có được giá trị trước đó. Giá trị thực là tham số được truyền cho N từ thời điểm hàm được gọi. Mục đích gọi hàm của chúng ta là gọi nó từ khối chính của chương trình. Trong trường hợp của chúng tôi, chúng tôi gọi nó từ một hàm int chính() Mong các lập trình viên tha thứ cho tôi vì nhận xét thiếu suy nghĩ như vậy. Đây là cách người mới bắt đầu cảm nhận đệ quy. Tôi hy vọng blog C++ dành cho người mới bắt đầu này hữu ích với ai đó và giúp ai đó hiểu khái niệm cơ bản về hàm đệ quy trong C++ Ghi chú. Trong bài viết này, cũng như bài trước, tôi không tính toán từ 1 đến N mà tính theo giá trị được nhập bên trong chương trình. Vấn đề là tôi không muốn viết thêm một dòng mã nào và cho rằng người dùng đã thành thạo trong việc nhập dữ liệu và hiển thị nó trên màn hình.
Varg nói: Xin chào, tôi thực sự không hiểu chức năng này thực hiện các phép tính như thế nào.
{ Theo hiểu biết của tôi, có 5 trong n, điều kiện không khớp, khi đó mã này được thực thi sum(n-1)+n, nghĩa là, thứ gì đó thu được trong ngoặc đơn bằng phép trừ được cộng vào 5, nhưng (5 - 1) + 5 và nếu vậy, điều gì dừng phép toán số học này:?: :?: :?: Giá trị trước đó là gì, nó đến từ đâu, nó bằng:?: :?: :?: Vâng, hầu hết mọi thứ đều như tôi đã hiểu (ở đoạn cuối bạn đã trình bày đệ quy))), nhưng câu hỏi vẫn là: làm thế nào để có được số tiền đó, sau đó được hiển thị trên màn hình? : (5) // Chúng tôi cho hàm 5, kiểm tra xem nó có bằng 1 không. không bằng, gọi lại hàm, truyền 5-1 vào đó 2-1 == 1, gọi hàm xong. Vâng, vâng, vâng, tôi không có thời gian để viết rằng tôi đã hiểu, mọi thứ đều chính xác, có điều gì đó chưa được giải quyết ngay lập tức. Cảm ơn bạn trang web tốt)) Và nó vẫn không hoàn toàn logic ở dòng thứ 8 nếu bạn thay đổi số trả về từ return 1 thành 2, số tiền thay đổi thành 16. Điều kiện này liên quan đến dòng thứ 9 như thế nào? :
Xin chào N2
…
Xin chào N10
…
Xin chào N1
…
Xin chào N10
Xin chào N10
…
Xin chào N14. Quan hệ tái diễn. Đệ quy và lặp lại
5. Cây cối
5.1. Định nghĩa cơ bản. Các cách khắc họa cây cối
a) Có một nút đặc biệt gọi là gốc của cây này.
b) Các nút còn lại (không bao gồm nút gốc) được chứa trong các tập con rời rạc theo cặp, mỗi tập con lần lượt là một cây. Cây được gọi là cây con của cây này.
5.2. Cây đi ngang qua
5.3. Biểu diễn cây trong bộ nhớ máy tính
6. Ví dụ về thuật toán đệ quy
6.1. Vẽ một cái cây
6.2. Tháp Hà Nội
Quá trình đó đòi hỏi đĩa lớn hơn chưa bao giờ thấy mình ở trên bất cứ điều gì ít hơn. Các nhà sư đang ở trong tình thế khó khăn: họ nên thay ca theo thứ tự nào? Cần phải cung cấp cho họ phần mềm để tính toán trình tự này.
2) Thay đổi Nđĩa thứ vào pin trống còn lại.
3) Chúng tôi chuyển ngăn xếp từ N-1 đĩa nhận được ở điểm (1) trên cùng N-đĩa thứ.6.3. Phân tích biểu thức số học
7.3. Xác định một nút cây theo số của nó
Câu hỏi kiểm soát
Nhiệm vụ
(b) trong bất kỳ cặp nào cũng có dấu ngoặc mở - đóng tương ứng, các dấu ngoặc được đặt đúng.
Viết chương trình đệ quy để tạo ra tất cả các cấu trúc khung thông thường có độ dài 2 N.
(b) nếu hai cấu trúc nhỏ hơn được viết tuần tự.
Văn học
2. N. Wirth. Thuật toán và cấu trúc dữ liệu.Nói ngắn gọn về đệ quy
Đệ quy là một hiện tượng khá phổ biến xảy ra không chỉ trong lĩnh vực khoa học mà còn trong Cuộc sống hàng ngày. Ví dụ: hiệu ứng Droste, tam giác Sierpinski, v.v. Một cách để xem đệ quy là hướng camera Web vào màn hình điều khiển máy tính, một cách tự nhiên, sau khi bật nó lên trước. Như vậy, camera sẽ ghi lại hình ảnh của màn hình máy tính và hiển thị lên màn hình này, nó sẽ giống như một vòng khép kín. Kết quả là chúng ta sẽ quan sát thấy thứ gì đó tương tự như một đường hầm.
Giả định rằng về mặt lý thuyết, người đọc đã quen thuộc với đệ quy và biết nó là gì. Trong bài viết này chúng ta sẽ chú ý hơn tới các bài toán đệ quy. Nhiệm vụ
Khi học đệ quy, cách hiểu đệ quy hiệu quả nhất là giải quyết vấn đề. Làm thế nào để giải quyết vấn đề đệ quy?
Trước hết, bạn cần hiểu rằng đệ quy là một dạng quá mức cần thiết. Nói chung, mọi thứ được giải lặp lại đều có thể được giải bằng đệ quy, nghĩa là sử dụng hàm đệ quy.
Cũng giống như một phép liệt kê (chu trình), đệ quy phải có điều kiện dừng - Trường hợp cơ sở (nếu không, cũng giống như một chu trình, đệ quy sẽ hoạt động mãi mãi - vô hạn). Điều kiện này là trường hợp đệ quy đi tới (bước đệ quy). Ở mỗi bước, một hàm đệ quy được gọi cho đến khi lệnh gọi tiếp theo kích hoạt điều kiện cơ bản và quá trình đệ quy dừng lại (hay đúng hơn là quay về cuộc gọi cuối chức năng). Toàn bộ giải pháp bắt nguồn từ việc giải quyết trường hợp cơ bản. Trong trường hợp hàm đệ quy được gọi để giải nhiệm vụ khó khăn(không phải trường hợp cơ bản) một số lệnh gọi hoặc bước đệ quy được thực hiện để giảm vấn đề xuống đơn giản hơn. Và cứ như vậy cho đến khi chúng ta nhận được giải pháp cơ bản.
Hãy xem xét điều này bằng cách sử dụng ví dụ về việc tìm giai thừa:
Viết mã
=============================
GIAI ĐOẠN Số 1 viết một chương trình trống
=============================
{
hệ thống ("cls");
trả về 0;
}
GIAI ĐOẠN số 2 ta viết ta viết chính hàm đệ quy
=========================================
int thực tế (int N )
{
nếu không thì trả về n * sự thật(n–1)
// ở đây hàm gọi chính nó
}
{
hệ thống ("cls");
cout<
getch();
trả về 0;
}
ddd
============
trả lại n * sự thật(n–1)
Tại sao tôi không viết bài tiếp theo mà viết bài trước? Khi các số được nhân lên, thì đầu tiên 0 * 1 ở đây là giá trị hiện tại của chúng ta là 1 và 0 là giá trị tính toán trước đó. Đây là toàn bộ bản chất của đệ quy, chúng tôi tính giá trị hiện tại bằng cách sử dụng giá trị trước đó, trong khi giá trị trước đó thu được bằng cách tính toán tương tự. Trình biên dịch tự tính toán giá trị trước đó và lưu giá trị này vào bộ nhớ. Tất cả những gì chúng ta cần làm là đưa ra hướng dẫn.
. Nhờ tính năng này của trình biên dịch, một hàm gặp phải lệnh gọi chính nó (trong trường hợp của chúng tôi sự thật(n–1)
) không ghi đè tham số được truyền cho Nđể tính hàm. Tham số được truyền tới N nó vẫn còn trong bộ nhớ. Trong trường hợp này, một vùng bộ nhớ khác được xác định bổ sung trong đó hàm đệ quy của chúng ta thực hiện các phép tính đệ quy để thu được kết quả trước đó.
nếu (n==1) trả về 1; // nếu giá trị mới là 1 thì chúng ta sẽ thêm nó bằng 1 chứ không phải với giá trị trước đó. bởi vì cái trước đó bằng không. và phép cộng 1+0 sẽ là vô hạn.
ngược lại trả về sum(n-1)+n; //nhưng nếu n>1 thì cộng nó vào giá trị trước đó, bằng tổng của tất cả các phần tử đến n
}
Tôi làm việc với Dev C++, ví dụ này hiển thị số tiền ==15, nếu bạn đếm nó như được viết trong ví dụ thì số tiền đó sẽ khác.
Tôi đã viết ở trên, hãy lấy (5-1)+5=4+5=9
1+2+3+4+5 = 15. Ví dụ đưa ra chính xác.
(5-1+(5)) //...
(4-1+(5-1+(5)))
(3-1+(4-1+(5-1+(5))))
(2-1+(3-1+(4-1+(5-1+(5)))))
(2-1+(3-1+(4-1+(5-1+(5))))) == 15
Đây là kết quả.
Ở đây kết quả của hàm số là hiệu của hai số đầu tiên và n là phần còn lại của vế phải
__________________________________
Bạn chỉ cần hiểu hàm một cách chính xác và chấp nhận nó như một giá trị được tính toán chứ không hiểu nó như một biến. Nó tương tự như một biến, nhưng gần với một hằng số được tính toán hơn, mặc dù nó không phải là một hằng số, nhưng việc nhận thức nó theo cách này chỉ đơn giản là thuận tiện hơn.
Với điều này cũng vậy, mọi thứ đều rõ ràng, chỉ cần trả về 2 sẽ cộng phần thiếu của nó vào tổng, có thể nói như vậy.
không phải ngôi sao thừa mà là hai ngôi sao này, và nếu bạn viết -3 thì khi cộng một lần sẽ trừ đi ba, v.v.
Toàn bộ logic là bất kỳ hàm đệ quy nào cũng cần có điểm trả về.
Mối liên hệ với dòng thứ chín là một số được truyền vào hàm tổng khi được gọi từ bên trong main; trong các lệnh gọi đệ quy, số này mỗi lần giảm đi một (n-1), kết quả này n-1 được kiểm tra xem có bằng nhau không. một và nếu đẳng thức đúng thì toàn bộ số tiền nhận được sẽ được cộng bằng số trong tờ khai đó. nếu không thì toàn bộ tổng số sẽ được cộng bằng n-1 mới này
