Hướng dẫn recursive function c++ - hàm đệ quy c ++
Trong hướng dẫn này, bạn sẽ học cách viết các chức năng đệ quy trong lập trình C với sự trợ giúp của một ví dụ. Show
Video: C đệ quy
Một hàm tự gọi được gọi là hàm đệ quy. Và, kỹ thuật này được gọi là đệ quy. Làm thế nào đệ quy hoạt động?void recurse() { ... .. ... recurse(); ... .. ... } int main() { ... .. ... recurse(); ... .. ... }làm việc đệ quy Việc đệ quy tiếp tục cho đến khi một số điều kiện được đáp ứng để ngăn chặn nó. Để ngăn chặn đệ quy vô hạn, nếu ... tuyên bố khác (hoặc cách tiếp cận tương tự) có thể được sử dụng khi một nhánh thực hiện cuộc gọi đệ quy và những cái khác thì không. Ví dụ: tổng số tự nhiên bằng cách sử dụng đệ quy
Đầu ra Enter a positive integer:3 sum = 6 Ban đầu, factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) return 1 return 2*1 = 2 return 3*2 = 6 return 4*6 = 24 return 5*24 = 1203 được gọi từ hàm factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) return 1 return 2*1 = 2 return 3*2 = 6 return 4*6 = 24 return 5*24 = 1204 có số được truyền dưới dạng đối số. Giả sử, giá trị của n bên trong factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) return 1 return 2*1 = 2 return 3*2 = 6 return 4*6 = 24 return 5*24 = 1203 ban đầu là 3. Trong cuộc gọi chức năng tiếp theo, 2 được chuyển đến hàm factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) return 1 return 2*1 = 2 return 3*2 = 6 return 4*6 = 24 return 5*24 = 1203. Quá trình này tiếp tục cho đến khi N bằng 0. Khi N bằng 0, điều kiện factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) return 1 return 2*1 = 2 return 3*2 = 6 return 4*6 = 24 return 5*24 = 1207 không thành công và phần factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) return 1 return 2*1 = 2 return 3*2 = 6 return 4*6 = 24 return 5*24 = 1208 được thực thi trả lại tổng số nguyên cuối cùng cho hàm factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) return 1 return 2*1 = 2 return 3*2 = 6 return 4*6 = 24 return 5*24 = 1204. Ưu điểm và bất lợi của đệ quyĐệ quy làm cho chương trình thanh lịch. Tuy nhiên, nếu hiệu suất là quan trọng, thay vào đó hãy sử dụng các vòng vì đệ quy thường chậm hơn nhiều. Điều đó đang được nói, đệ quy là một khái niệm quan trọng. Nó thường được sử dụng trong cấu trúc dữ liệu và thuật toán. Ví dụ, thông thường sử dụng đệ quy trong các vấn đề như truyền tải cây. 2.3 & nbsp; Đệ quy - Đệ QUYÝ tưởng gọi một han từ bên trong một haH kác lập tức gợi đến Khả năng một ha Cơ chế ha Ệ quy là một kĩ thuật lập trì , Cho Đến Phương Pháp Xử Lý Tín Hiệu Số Biến đổi Fourier nhanh để xử lý tín hiệu (Chương 9). Chương trình Đệ QUY ĐầU Tin.Chương trình Chào thế giớiCho Đệ QUY Là HÀM TínH GIIA THừ N! = N × (n-1) × (n-2) × ... × 2 × 1 Ta thoại thể dễ dàng tính n! bằng một vngng for, NHưng Cách Đó vẫn Chưa Đơn Giản public static int factorial(int N) { if (N == 1) return 1; return N * factorial(N-1); } Bạn bạn thể tự chứng Minhng ha factorial()TRả Về 1 = 1! Khi Nbằng 1 và nếu nó tính đếm (N-1)! = (N-1) × (n-2) × ... × 2 × 1 thì nó cũng tính đaog giá trị N! = N × (N-1)! = N × (n-1) × (n-2) × ... × 2 × 1 Ta đó là thể lần bước quá trình tính toán đó factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) return 1 return 2*1 = 2 return 3*2 = 6 return 4*6 = 24 return 5*24 = 120 CÀi ĐặT HO không ()
QUY Nạp Toán Học.Lập trình đệ quy đó quan hệ trực tiếp với quy nạp toán học, một kĩ thul Việc Dùng QUY NạP Để Chứng MIH MộT Phát Biểu Về Một
Một chứng MINH NH N. Thuật Toán Euclid.Ước Số Chung lớn NHất - Ưu điểm chung lớn nhất (GCD) Ví dụ, ucln của 102 vào Taó thể tính ucln - gcd một cách rất hiệu quảu sử dụng tính chất Sau đó Nếu p > q, thì UCLN(p,q) = UCLN(q, p % q). Phương thức static gcd() trong Euclid.java là một hàm đệ quy ngắn gọn với bước đệ quy dựa vào tính chất trên. gcd(1440, 408) gcd(408, 216) gcd(216, 192) gcd(192, 24) gcd(24, 0) return 24 return 24 return 24 return 24 return 24 Bài toán Tháp Hà Nội.Một bài giảng về đệ quy không thể hoàn chỉnh nếu không nhăc đến bài toán cổ Tháp Hà Nội. Ta có ba cột và n đĩa có thể xếp lồng vào các cột đó. Các cái đĩa đó có kích thước khác nhau và ban đầu được xếp vào một cột trong số đó, theo thứ tự đĩa lớn bên dưới, đĩa nhỏ bên trên (đĩa n nằm dưới đáy và đĩa 1 trên đỉnh). Nhiệm vụ là di chuyển chồng đĩa sang một cột khác, tuân thủ các quy tắc sau:
Để giải bài toán, mục tiêu của ta là tạo ra một chuỗi lệnh di chuyển đĩa. Giả sử các cột được xếp thành hàng, mỗi lệnh di chuyển đĩa quy định 2 thông tin: số hiệu đĩa cần di chuyển và hướng di chuyển (trái hay phải). Với một đĩa nằm trên cột bên trái, lệnh chuyển sang trái có tác dụng xoay vòng chuyển nó sang cột bên phải; với một đĩa nằm trên cột phải, lệnh di chuyển sang phải sẽ xoay vòng chuyển nó sang cột bên trái. Exponential time - thời gian chạy lũy thừa.Một truyền thuyết nói rằng trong một ngôi đền có một nhóm các nhà sư ngồi giải bài toán Tháp Hà Nội với 64 cái đĩa bằng vàng trên ba chiếc kim bằng kim cương. Khi các nhà sư này giải xong thì ngày đó sẽ là ngày tận thế. Ta có thể ước lượng thời gian cho đến ngày tận thế đó (giả sử truyền thuyết kia đúng). Nếu ta định nghĩa hàm T(n) là số lệnh di chuyển mà chương trình TowersOfHanoi.java sinh ra để di chuyển n đĩa từ một cột sang một cột khác, thì hàm đệ quy cho thấy T(n) phải thỏa mãn hệ phương trình sau: T(n) = 2 T(n - 1) + 1 với n > 1, và T(1) = 1 Một hệ phương trình như vậy trong toán rời rạc được gọi là một quan hệ đệ quy - recurrence relation. Ta thường dùng chúng để rút ra một biểu thức dạng đóng là công thức cho một đại lượng quan tâm. Chẳng hạn, T(1) = 1, T(2) = 3, T(3) = 7, and T(4) = 15. Tổng quát, T(n) = 2^n - 1. Khi biết giá trị của T(n), ta có thể ước lượng thời gian cần thiết để thực hiện tất cả các bước di chuyển. Nếu cứ mỗi giây, các nhà sư lại chuyển được một đĩa, họ sẽ cần 1 tuần để giải xong bài toán 20 đĩa, hơn 31 năm cho bài toán 30 đĩa, và hơn 348 thế kỉ cho một bài toán 40 đĩa (giả thiết rằng họ không di chuyển nhầm bước nào). Bài toán 64 đĩa sẽ cần đến hơn 5,8 tỷ thế kỷ. Gray code - Mã Gray.Nhà biên kịch Samuel Beckett đã viết một vở kịch có tên Quad với tính chất sau: Mở màn là một sân khấu trống rỗng, mỗi thời điểm chỉ có nhiều nhất 01 nhân vật vào hoặc ra sân khấu. Nhưng mỗi nhóm nhân vật xuất hiện trên sân khấu đúng 01 lần. Vở kịch có bốn nhân vật. Do đó có 2^4 = 16 nhóm nhân vật khác nhau, nghĩa là 16 tập con của tập hợp gồm 4 phần tử; Cái tên của vở kịch xuất phát từ đó. Hỏi Beckett làm thế nào để tạo ra hướng dẫn vào ra cho vở kịch này. Nếu số nhân vật là 5 hoặc nhiều hơn thì ta làm cách nào? (enter: ra sân khấu, exit: vào bên trong cánh gà - ra khỏi sân khấu). Mã Gray n-bit là một danh sách gồm 2^n số nhị phân n-bit khác nhau sao cho mỗi số trong danh sách đều khác số liền trước nó đúng 01 bit. Mã Gray áp dụng trực tiếp cho bài toán của Beckett vì ta có thể coi mỗi số nhị phân trong dãy đại diện cho một tập con của n phần tử, với mỗi bit đại diện cho việc số tự nhiên tương ứng với vị trí của bit đó có nằm trong tập con đó hay không. Việc thay đổi giá trị của một bit từ 0 đến 1 tương ứng với việc một số nguyên được đưa vào tập con; thay đổi từ 1 về 0 ứng với việc một số tự nhiên ra khỏi tập con. Ta sinh mã Gray bằng cách nào? Một kế hoạch đệ quy khá tương tự với thuật toán đã dùng cho bài Tháp Hà Nội. Bộ số nhị phân n bit biểu diễn mã Gray được định nghĩa một cách đệ quy như sau:
Bộ mã 0-bit được định nghĩa là dãy rỗng, Bộ mã 1-bit gồm 2 từ: 0 và 1. Sau khi nghĩ cẩn thận một chút, ta sẽ thấy định nghĩa đệ quy dẫn đến cài đặt tại Beckett.java cho chương trình in ra hướng dẫn sân khấu của Beckett. Recursive graphics - Đồ họa đệ quy.Một thuật toán vẽ đệ quy đơn giản có thể đem lại một hình ảnh rất phức tạp. Ví dụ, một hình H-tree bậc n được định nghĩa như sau: Trường hợp cơ bản, n = 0, là hình rỗng không. Bước đệ quy là vẽ ba đoạn thẳng tạo thành hình chữ H trong phạm vi hình vuông đơn vị, và bốn hình H-tree bậc n-1 tại bốn đầu mút của chữ H vừa vẽ. Điều kiện bổ sung là các hình H-tree bậc n-1 nằm tại tâm của bốn mảng 1/4 của hình vuông nói trên, với kích thước giảm còn một nửa. Chương trình Htree.java nhận n là tham số dòng lệnh và vẽ một hình H-tree bậc n bằng thư viện StdDraw. Brownian bridge - Cầu Brown.H-tree là một ví dụ đơn giản của fractal: một hình hình học có thể chia thành các phần mà mỗi phần là (xấp xỉ) một bản sao thu nhỏ của hình ban đầu. Nghiên cứu về fractals đóng một vai trò quan trọng và dài lâu trong nghệ thuật, phân tích kinh tế, và các phát kiến khoa học. Các nghệ sỹ và nhà khoa học sử dụng fractal để xây dựng các mô hình xúc tích của các hình dạng phức tạp xuất hiện trong tự nhiên mà hình học truyền thống không thể mô tả được, chẳng hạn như mây, thực vật, núi, lưu vực sông, da người, và nhiều thứ khác. Các nhà kinh tế học cũng dùng fractal để mô hình hóa các đồ thị hàm số của các chỉ số kinh tế. Chương trình Brownian.java tạo một đồ thị hàm số xấp xỉ một ví dụ đơn giản được gọi là cây cầu Brown (Brownian bridge) và các hàm liên quan. Bạn có thể coi đồ thị này như là một đường nối ngẫu nhiên giữa hai điểm, từ (x0, y0) tới (x1, y1), được điều khiển bởi một số tham số. Cài đặt này dựa trên phương pháp thay điểm giữa (midpoint displacement method), đó là một thuật toán đệ quy cho việc vẽ đồ thị trong khoảng [x0, x1]. Trường hợp cơ bản (khi độ dài của khoảng nhỏ hơn một ngưỡng chấp nhận cho trước) là vẽ một đoạn thẳng nối hai điểm. Bước đệ quy là chia khoảng quan tâm làm đôi, quy trình như sau:
Đường cong được điều khiển bởi hai tham số: volatility (giá trị ban đầu của variance) điều khiển khoảng cách tối đa của đồ thị tới đường thẳng nối hai điểm, và Hurst exponent điều khiển độ mịn của đường cong. Ta kí hiệu Hurst exponent bằng H và chia variance cho 2^(2H) tại mỗi tầng đệ quy. Khi H bằng 1/2 (nghĩa là chia đôi ở mỗi tầng) độ lệch chuẩn sẽ là một hằng số đối với toàn bộ đường cong: trong trường hợp này, đường cong là một đường dạng cầu Brown. Các lỗi thường gặp khi dùng đệ quy.Với đệ quy, bạn có thể viết những chương trình đẹp và ngắn gọn mà khi chạy nó lại thất bại thảm hại.
Q + AQ. Có khi nào vòng lặp là cách duy nhất để giải một bài toán? Có khi nào vòng lặp là cách duy nhất để giải một bài toán? A. Không, bất cứ vòng lặp nào cũng có thể thay thế bằng một hàm đệ quy, tuy nhiên phiên bản đệ quy có thể đòi hỏi quá nhiều bộ nhớ. Không, bất cứ vòng lặp nào cũng có thể thay thế bằng một hàm đệ quy, tuy nhiên phiên bản đệ quy có thể đòi hỏi quá nhiều bộ nhớ. Q. Có khi nào đệ quy là cách duy nhất để giải một bài toán? Có khi nào đệ quy là cách duy nhất để giải một bài toán? A. Không, hàm đệ quy bất kì đều có thể thay thế bằng một phiên bản dùng vòng lặp. Ở mục 4.3, ta sẽ thấy cách trình biên dịch sinh mã cho các lời gọi hàm bằng cách sử dụng một cấu trúc dữ liệu gọi là stack. Không, hàm đệ quy bất kì đều có thể thay thế bằng một phiên bản dùng vòng lặp. Ở mục 4.3, ta sẽ thấy cách trình biên dịch sinh mã cho các lời gọi hàm bằng cách sử dụng một cấu trúc dữ liệu gọi là stack. Q. Tôi nên ưu tiên chọn cái gì hơn, đệ quy hay vòng lặp? Tôi nên ưu tiên chọn cái gì hơn, đệ quy hay vòng lặp? A. Hãy chọn cách nào cho bạn code đơn giản dễ hiểu hơn, hoặc hiệu quả hơn. Hãy chọn cách nào cho bạn code đơn giản dễ hiểu hơn, hoặc hiệu quả hơn. Q. Tôi lo ngại về việc mã đệ quy dùng quá nhiều bộ nhớ và tính toán lại quá nhiều lần. Ngoài ra còn nên để ý những vấn đề gì nữa không? Tôi lo ngại về việc mã đệ quy dùng quá nhiều bộ nhớ và tính toán lại quá nhiều lần. Ngoài ra còn nên để ý những vấn đề gì nữa không? A. Cực kì cẩn trọng trong việc tạo mảng trong mã đệ quy. Lượng bộ nhớ sử dụng có thể tăng lên rất rất nhanh, cũng như thời gian tiêu tốn cho việc quản lý phần bộ nhớ đó. Cực kì cẩn trọng trong việc tạo mảng trong mã đệ quy. Lượng bộ nhớ sử dụng có thể tăng lên rất rất nhanh, cũng như thời gian tiêu tốn cho việc quản lý phần bộ nhớ đó. Bài tập
Creative Exercises
Bài tập web
|