Một trong những công cụ cơ bản nhất trong lập trình là vòng lặp. Mặc dù có nhiều loại vòng lặp khác nhau nhưng hầu hết mỗi loại vòng lặp đều có chức năng cơ bản giống nhau. lặp lại dữ liệu để phân tích hoặc thao tác với nó. Đệ quy là một loại hàm phổ biến khác và mặc dù nó cũng có thể phân tích và thao tác các chuỗi dữ liệu tương tự như một vòng lặp, nhưng trong nhiều trường hợp, đệ quy có thể ít được hiểu hơn và thường có thể hơi khó hiểu. Hầu như tất cả các hàm đệ quy có thể được viết lại dưới dạng vòng lặp và ngược lại. Tuy nhiên, mỗi loại chức năng đều có ưu điểm và nhược điểm và biết khi nào nên sử dụng loại này hơn loại kia là điều chúng ta sẽ xem xét tại đây. Trong bài đăng sau, chúng tôi sẽ cố gắng trả lời các câu hỏi sau
- Vòng lặp For là gì?
- Đệ quy là gì?
- Một ví dụ thực tế của mỗi phương pháp là gì?
- Khi nào nên sử dụng một trong hai phương pháp?
- Cấu trúc dữ liệu đệ quy là gì?
Hãy bắt đầu với phương pháp thường có vẻ đơn giản hơn trong hai phương pháp, vòng lặp
Đối với vòng lặp
Đối với Luồng vòng lặp
Vòng lặp for được sử dụng để lặp qua một chuỗi [đó là danh sách, bộ dữ liệu, từ điển, tập hợp hoặc chuỗi]. Một vòng lặp for kết thúc bất cứ khi nào nó đến cuối chuỗi dữ liệu
Hãy tưởng tượng chúng ta muốn cộng tất cả các số dưới 5 và lấy tổng. Chắc chắn rồi, chúng ta chỉ cần thêm 1+2+3+4+5. Nhưng nếu chúng ta biến nó thành một hàm, nó cho phép chúng ta sử dụng lại hàm đó để cộng các số dưới 10 hoặc 20 hoặc bất cứ thứ gì. Có thể có trường hợp chúng ta cần thêm hai giá trị mà không biết giá trị đó là gì, do đó, có một hàm trả về tổng các số bên dưới một giá trị nhất định có thể hữu ích
Trong trường hợp này, chúng ta có thể làm điều gì đó như sau
Để làm cho vòng lặp này hoạt động, chúng tôi cần lưu trữ tất cả các số dưới dạng danh sách để chúng tôi có thể lặp lại từng phần tử và thêm nó vào tổng số
Hãy xem điều này có thể trông như thế nào trong mã thực tế
def getTotal[n]. tổng = 0 cho số trong danh sách [phạm vi [n + 1]]. in numbertotal = total + numberreturn total
in getTotal[5]
Chức năng của chúng tôi bắt đầu bằng cách lấy một số làm tham số. Ở đây, chúng tôi sẽ sử dụng 5 làm tham số của chúng tôi. Sau đó, chúng tôi sẽ đặt tổng số của chúng tôi bằng 0. Cuối cùng, chúng tôi lặp lại danh sách các số từ 0 đến n+1. Chúng tôi làm n+1 ở đây, bởi vì list[range[n]] sẽ cho chúng tôi các số nhỏ hơn n, nhưng không bao gồm n, trong trường hợp này sẽ là 0,1,2,3,4. Vì chúng tôi muốn bao gồm 5, chúng tôi sẽ sử dụng ____4
Nếu chúng tôi chạy mã này, chúng tôi có thể thấy rằng ở mỗi lần lặp lại, chúng tôi có số mà chúng tôi mong đợi và chúng tôi được trả về tổng số
Bản in ra của chúng tôi sẽ như thế này
01234515
Đệ quy xảy ra khi bất kỳ hàm nào gọi chính nó. Một trong những điểm khác biệt lớn giữa đệ quy và vòng lặp là cách mà một hàm đệ quy kết thúc. Trong ví dụ trên, vòng lặp for kết thúc ở cuối chuỗi mà nó đang lặp. Tuy nhiên, một hàm đệ quy có thể tiếp tục vô thời hạn vì nó không nhất thiết phải có một chuỗi dữ liệu. Thay vào đó, các hàm đệ quy có cái được gọi là điều kiện cơ sở. Điều kiện cơ sở là điều kiện sẽ kết thúc vòng lặp nếu điều kiện được đáp ứng
Hãy lấy ví dụ trên và viết lại bằng đệ quy. Nhìn bề ngoài, đây có thể trông như thế này
Tại mỗi hàm, hàm đó sẽ tự gọi chính nó với các đầu vào mới hoặc trả về một giá trị
Hãy cùng xem mã này có thể trông như thế nào trong mã thực tế
def getTotal[n, tổng]. in nif n == 0. # tổng điều kiện trả về cơ sở khác. trả về getTotal[n-1, [tổng+[n]]]
in getTotal[5, 0]
Ở đây, chúng ta có thể chuyển vào một số bắt đầu và một biến tổng. Khi hàm được gọi lần đầu, tổng là 0 và số là 5. Chúng tôi kiểm tra xem nếu số là 0. Nếu không, chúng tôi gọi lại hàm…nhưng lần này thay vì gọi nó với 0 và 5, chúng tôi gọi nó với 5–1 và 0+5, và lặp lại quy trình này cho đến khi số đó bằng 0, lúc đó chúng tôi trả về tổng
Tính lãi kép bằng đệ quy và Vòng lặp
Bài tập khó hơn một chút, hãy xác định giá trị của một khoản vay hoặc một khoản đầu tư với lãi kép. Để xác định giá trị này sẽ là bao nhiêu, chúng ta cần 4 điều
- Thời lượng tính bằng năm
- Lãi suất
- Số Lần Tích Lũy Mỗi Năm
- Số tiền gốc
Công thức tính lãi kép như sau
Tuy nhiên, điều này sẽ tính toán toàn bộ số tiền cùng một lúc. Thay vào đó, chúng tôi muốn thực hiện nó trong một vòng lặp hoặc với đệ quy. Trong trường hợp đó, biến thời gian [nt] của chúng ta sẽ thực sự được xử lý trong các lần lặp lại
Trong cả hai phương pháp, chúng tôi sẽ sử dụng từng số này làm biến, vì vậy chúng tôi có thể tiếp tục và khai báo chúng và sử dụng các biến giống nhau cho từng phương thức
Các biến có thể được định nghĩa theo cách này
durationInYears = 10interestRate =. 06 tổng hợp mỗi năm = 12 số tiền gốc = 4000
— — Tính lãi gộp với vòng lặp
Để làm cho việc tính toán dễ dàng hơn trong một vòng lặp, điều đầu tiên chúng ta sẽ làm là lấy tổng số lần tiền lãi sẽ được gộp. Nếu nó sẽ được gộp hàng tháng, như chúng ta đã đặt nó trong các biến của mình và tổng số năm là 10, thì kết quả sẽ là 120 hoặc 10*12. Bây giờ, chúng ta có thể lặp qua từng số trong phạm vi đó, thực hiện phép tính lãi gộp cho mỗi lần lặp và cộng số đó vào số tiền gốc
Đây là mã có thể trông như thế nào
xác định lãi kép [tiền gốc, lãi gộp, thời hạn, tỷ lệ]. tổng cộng = thời lượng * gộp cho tôi trong phạm vi [1, [tổng cộng + 1]]. tiền gốc = tiền gốc*[1+[tỷ lệ/góp]] tiền gốc trả lại
in [Lãi suất kép [Số tiền gốc, lãi gộp mỗi năm, thời lượng trong năm, lãi suất]]
Sự khác biệt duy nhất giữa ví dụ này và ví dụ đơn giản hơn là chúng ta chỉ thực hiện thêm một vài phép tính ở mỗi lần lặp lại. Thay vì một chuỗi 5, chúng tôi thực sự đang lặp lại các số từ 1 đến 120, biểu thị tổng số lần tiền lãi sẽ được gộp
Nếu chúng ta ghi lại đầu ra, chúng ta sẽ nhận được giá trị là
7277. 58693613
— — Tính toán lãi gộp với đệ quy
Trong ví dụ trước, chuỗi dữ liệu của chúng tôi là 120, đại diện cho số lần số tiền gốc sẽ được gộp. Sau khi đến cuối dãy, vòng lặp sẽ kết thúc. Với đệ quy, chúng ta có thể thiết lập nó theo cách tương tự. Chúng tôi có thể cung cấp cho chức năng tổng thời lượng và về cơ bản có hai điều kiện
- Điều kiện 1. Thời lượng không phải là 0
Thực hiện phép tính lãi kép. Thêm iterest mới vào số tiền gốc. Trừ 1 từ tổng thời lượng. Gọi phụ lại với số tiền gốc mới và thời hạn mới
- Điều kiện 2 [điều kiện cơ sở]. Thời lượng là 0
Trả lại số tiền gốc
Trong ví dụ đệ quy trước của chúng tôi, chúng tôi bắt đầu từ 5 và kết thúc hàm khi nó đạt 0
Ở đây, chúng tôi sẽ làm điều tương tự, nhưng thay vào đó sẽ bắt đầu từ 120
xác định đệ quy phức hợp [tiền gốc, gộp, thời lượng, tỷ lệ, số lần truy cập]. nếu numberOfRecursions == 0. totalDuration = gộp * durationelif numberOfRecursions. = 0. tổng thời lượng = thời lượng nếu thời lượng == 0. trả lại hiệu trưởng. thời lượng mới = tổng thời lượng - 1 số tiền = tiền gốc*[1+[tỷ lệ/ghép gộp]] trả về gộpRecursion[số tiền, gộp, thời lượng mới, tỷ lệ, 1]
in [compoundRecursion[Số tiền gốc, gộp theo năm, thời lượng trong năm, lãi suất, 0]]
Tại đây, Chúng tôi gọi lại chức năng hoặc trả lại số tiền gốc đã sửa đổi. Mỗi lần chúng ta gọi hàm mới, chúng ta gọi nó, nhưng vượt qua thời lượng trừ đi 1. Khi thời lượng bằng 0, thì chúng tôi chỉ trả lại số tiền gốc
Khi nào sử dụng đệ quy
Việc sử dụng đệ quy hoặc vòng lặp có thể phụ thuộc phần lớn vào ngôn ngữ chúng tôi đang sử dụng hoặc những gì chúng tôi định giải quyết. Ví dụ: trong JavaScript, sử dụng đệ quy có thể dẫn đến lỗi khung ngăn xếp khi đạt đến giới hạn ngăn xếp trước khi đáp ứng điều kiện cơ sở. Nếu đúng như vậy, một vòng lặp có thể hoạt động tốt hơn
Ví dụ trên cũng cho chúng ta một ví dụ tuyệt vời về thời điểm đệ quy có thể hoạt động tốt hơn nhiều so với vòng lặp
Hãy tưởng tượng rằng thay vì chỉ theo dõi các con số, như chúng ta đang làm ở trên, chúng ta cũng muốn theo dõi các dữ liệu khác ở mỗi khoảng gộp. Ví dụ: chúng tôi có thể muốn xem xét các khoản thanh toán định kỳ sẽ ảnh hưởng như thế nào đến thời hạn của khoản vay. Chúng tôi có thể muốn kết thúc vòng lặp trước khi trình tự kết thúc. Nếu tổng số lần lãi suất của một khoản vay sẽ được cộng gộp là 120, thì độ dài của danh sách của chúng ta là 120. Tuy nhiên, nếu số tiền cho vay là 0 chỉ sau 100 lần lặp, chúng tôi có 20 phần tử danh sách không sử dụng và không cần thiết treo ở cuối danh sách của chúng tôi. Kịch bản vòng lặp phức tạp hơn nữa là giá trị của các biến như số tiền cho vay phụ thuộc vào giá trị của số tiền cho vay ở lần lặp trước. Nó không phải là điều này đặc biệt khó khăn, nhưng nó lộn xộn
Trực quan, đây là cách những vấn đề này có thể trông như thế nào
Cấu trúc dữ liệu đệ quy
Đó chính xác là khi cấu trúc dữ liệu đệ quy có ích. Một cấu trúc dữ liệu là đệ quy nếu nó có thể được định nghĩa theo một phiên bản nhỏ hơn của chính nó. Danh sách là một ví dụ về cấu trúc dữ liệu đệ quy
Ví dụ: hãy lấy danh sách sau
Bây giờ, hãy tạo hai danh sách nhỏ hơn từ danh sách ban đầu của chúng ta
Nếu chúng tôi in cả hai danh sách, chúng tôi sẽ nhận được như sau
Lý do điều này rất hiệu quả là với các hàm đệ quy và cấu trúc dữ liệu đệ quy, chúng ta có thể sửa đổi toàn bộ danh sách hoặc một phần nhỏ hơn của danh sách lớn hơn cùng một lúc. Khi chúng tôi nghĩ về vấn đề này với vòng lặp, chúng tôi chỉ có thể thay đổi một giá trị tại một chỉ mục tại một thời điểm
Như một ví dụ về cách thực hiện việc này, hãy xem xét những điều sau đây
nếu chúng tôi đã lưu các phần nhỏ hơn này của danh sách lớn hơn, thì chúng tôi có thể gọi cùng một chức năng [đệ quy] và gửi cho nó danh sách nhỏ hơn [cấu trúc dữ liệu đệ quy]
Hãy xem điều này có thể hoạt động như thế nào với ví dụ lãi kép trước đây của chúng tôi
def đệ quyData[dữ liệu]. # Điều kiện cơ sở [ nếu số tiền gốc == 0 hoặc nếu thời hạn == 0]
# Else Condition [ recalculate the times compounded, duration & principal amount]
in [đệ quyData [mảng]]
Chức năng của chúng tôi về cơ bản sẽ bao gồm một câu lệnh if other. Mặc dù nó có thể trở nên phức tạp hơn nếu chúng ta muốn, nhưng có lẽ chúng ta có thể hoàn thành tất cả những gì chúng ta muốn làm ở đây. Cuối cùng, chúng tôi muốn trả lại dữ liệu đã hoàn thành, sẽ có số tiền cho vay và khoản thanh toán hiện tại tại mỗi khoảng thời gian mà khoản vay được gộp
Đầu ra dữ liệu của chúng tôi có thể trông như thế này
[{'ghép lần'. 0,'thời lượng còn lại'. 10,'lãi suất'. . 06,'thanh toán hiện tại'. 100,'gộp mỗi năm'. 12,'tiền gốc'. 4000},{'nhân đôi'. 1,'thời lượng còn lại'. 10,'lãi suất'. . 06,'thanh toán hiện tại'. 100,'gộp mỗi năm'. 12,'tiền gốc'. 3900}]
Với suy nghĩ này và cũng xem lại các ví dụ về danh sách nhỏ hơn của chúng tôi, đây là cách quá trình này có thể sẽ diễn ra
Với mỗi lần gọi đệ quy, chúng ta sẽ lấy phần tử đầu tiên trong mảng từ danh sách. Sau đó, chúng tôi sẽ sửa đổi các giá trị của phần tử đó và gọi lại hàm, nhưng lần này chuyển qua mảng [. 1] và mảng [1. ] làm tham số. Như chúng ta có thể thấy, ở giữa danh sách, chúng ta sẽ có hai danh sách có cùng kích thước và cuối cùng, chúng ta sẽ chuyển và sửa đổi đầy đủ tất cả các thành phần của danh sách đầu tiên và thêm tất cả chúng vào danh sách thứ hai. Tiếp theo, chúng ta sẽ từng bước tạo chức năng này bằng mã thực tế
bước 1. Tạo mảng
durationInYears = 10compoundedPerYear = 12
mảng = [{'nhân đôi'. 0,'thời lượng còn lại'. 10,'lãi suất'. . 06,'thanh toán hiện tại'. 50,'gộp mỗi năm'. 12,'tiền gốc'. 4000, 'tổng gộp'. gộpPerYear*durationInYears}]*[compoundedPerYear*durationInYears]
Tại thời điểm này, chúng tôi có một mảng độ dài của tổng số lần khoản vay sẽ được gộp. Mỗi phần tử chứa cùng một dữ liệu mà chúng ta sẽ thay đổi theo cách đệ quy
Bước 2. Tạo hàm & điều kiện cơ sở
def đệ quyData[inputArr, outputArr]. if len[inputArr] == 0 hoặc inputArr[-1]['số tiền gốc']