Sự khác biệt chính - Đệ quy và Lặp lại
Đệ quy và lặp lại có thể được sử dụng để giải quyết các vấn đề lập trình. Cách tiếp cận để giải quyết vấn đề bằng cách sử dụng đệ quy hoặc lặp phụ thuộc vào cách giải quyết vấn đề. Sự khác biệt chính giữa đệ quy và lặp là đệ quy là một cơ chế để gọi một hàm trong cùng một hàm trong khi phép lặp là thực hiện một tập lệnh lặp đi lặp lại cho đến khi điều kiện đã cho là đúng. Đệ quy và Lặp lại là các kỹ thuật chính để phát triển các thuật toán và xây dựng các ứng dụng phần mềm.
Đệ quy là gì?
Khi một hàm gọi chính nó trong hàm, nó được gọi là Đệ quy. Có hai loại đệ quy. Chúng là đệ quy hữu hạn và đệ quy vô hạn. Đệ quy hữu hạn có điều kiện kết thúc. Đệ quy vô hạn không có điều kiện kết thúc.
Đệ quy có thể được giải thích bằng cách sử dụng chương trình để tính giai thừa.
n!=n(n-1) !, nếu n>0
n!=1, nếu n=0;
Tham khảo đoạn mã dưới đây để tính giai thừa của 3 (3!=321).
intmain () {
int value=Giai thừa (3);
printf (“Giai thừa là% d / n”, giá trị);
trả về 0;
}
intfactorial (intn) {
nếu (n==0) {
trả về 1;
}
khác {
return ngiai thừa (n-1);
}
}
Khi gọi giai thừa (3), hàm đó sẽ gọi giai thừa (2). Khi gọi giai thừa (2), hàm đó sẽ gọi giai thừa (1). Khi đó giai thừa (1) sẽ gọi giai thừa (0). giai thừa (0) sẽ trả về 1. Trong chương trình trên, điều kiện n==0 trong “if block” là điều kiện cơ sở. Theo Tương tự, hàm giai thừa được gọi đi gọi lại.
Các hàm đệ quy có liên quan đến ngăn xếp. Trong C, chương trình chính có thể có nhiều chức năng. Vì vậy, main () là hàm gọi, và hàm được gọi bởi chương trình chính là hàm được gọi. Khi chức năng được gọi, điều khiển được trao cho chức năng được gọi. Sau khi thực hiện xong chức năng, điều khiển được trả lại cho main. Sau đó chương trình chính tiếp tục. Vì vậy, nó tạo ra một bản ghi kích hoạt hoặc một khung ngăn xếp để tiếp tục thực thi.
Hình 01: Đệ quy
Trong chương trình trên, khi gọi giai thừa (3) từ main, nó tạo ra một bản ghi kích hoạt trong ngăn xếp cuộc gọi. Sau đó, khung ngăn xếp giai thừa (2) được tạo trên đầu ngăn xếp, v.v. Bản ghi kích hoạt lưu giữ thông tin về các biến cục bộ, v.v. Mỗi khi hàm được gọi, một tập hợp các biến cục bộ mới được tạo trên đầu ngăn xếp. Các khung ngăn xếp này có thể làm chậm tốc độ tăng tốc. Tương tự như vậy trong đệ quy, một hàm gọi chính nó. Độ phức tạp thời gian cho một hàm đệ quy được tìm thấy bằng số lần, hàm được gọi. Độ phức tạp thời gian cho một lệnh gọi hàm là O (1). Đối với n số cuộc gọi đệ quy, độ phức tạp về thời gian là O (n).
Lặp lại là gì?
Lặp lại là một khối lệnh lặp đi lặp lại cho đến khi điều kiện đã cho là đúng. Có thể thực hiện lặp lại bằng cách sử dụng “vòng lặp for”, “vòng lặp do-while” hoặc “vòng lặp while”. Cú pháp "vòng lặp for" như sau.
cho (khởi tạo; điều kiện; sửa đổi) {
// câu lệnh;
}
Hình 02: “cho sơ đồ vòng lặp”
Bước khởi tạo thực hiện đầu tiên. Bước này là khai báo và khởi tạo các biến điều khiển vòng lặp. Nếu điều kiện là đúng, các câu lệnh bên trong dấu ngoặc nhọn sẽ thực thi. Những câu lệnh đó thực thi cho đến khi điều kiện là đúng. Nếu điều kiện sai, điều khiển chuyển sang câu lệnh tiếp theo sau “vòng lặp for”. Sau khi thực hiện các câu lệnh bên trong vòng lặp, điều khiển sẽ chuyển đến phần sửa đổi. Đó là cập nhật biến điều khiển vòng lặp. Sau đó, điều kiện được kiểm tra lại. Nếu điều kiện là đúng, các câu lệnh bên trong dấu ngoặc nhọn sẽ thực thi. Bằng cách này, "vòng lặp for" sẽ lặp lại.
Trong “vòng lặp while”, các câu lệnh bên trong vòng lặp thực thi cho đến khi điều kiện là đúng.
trong khi (điều kiện) {
// câu lệnh
}
Trong vòng lặp “do-while”, điều kiện được kiểm tra ở cuối vòng lặp. Vì vậy, vòng lặp thực hiện ít nhất một lần.
làm {
// câu lệnh
} trong khi (điều kiện)
Chương trình tìm giai thừa của 3 (3!) Bằng phép lặp (“vòng lặp for”) như sau.
int main () {
intn=3, giai thừa=1;
inti;
cho (i=1; i<=n; i ++) {
factorial=Giai thừai;
}
printf (“Giai thừa là% d / n”, giai thừa);
trả về 0;
}
Điểm giống nhau giữa Đệ quy và Lặp lại là gì?
- Cả hai đều là kỹ thuật để giải quyết một vấn đề.
- Nhiệm vụ có thể được giải quyết trong đệ quy hoặc lặp lại.
Sự khác biệt giữa Đệ quy và Lặp lại là gì?
Đệ quy so với Lặp lại |
|
| Đệ quy là một phương pháp gọi một hàm trong cùng một hàm. | Lặp lại là một khối lệnh lặp lại cho đến khi điều kiện đã cho là đúng. |
| Độ phức tạp của không gian | |
| Độ phức tạp không gian của chương trình đệ quy cao hơn so với lặp. | Độ phức tạp của không gian thấp hơn trong các lần lặp. |
| Tốc độ | |
| Thực thi đệ quy chậm. | Thông thường, lặp đi lặp lại nhanh hơn đệ quy. |
| Điều kiện | |
| Nếu không có điều kiện kết thúc, có thể có một đệ quy vô hạn. | Nếu điều kiện không bao giờ trở thành sai, nó sẽ là một lần lặp vô hạn. |
| Chồng | |
| Trong đệ quy, ngăn xếp được sử dụng để lưu trữ các biến cục bộ khi hàm được gọi. | Trong một lần lặp lại, ngăn xếp không được sử dụng. |
| Khả năng đọc mã | |
| Chương trình đệ quy dễ đọc hơn. | Chương trình lặp khó đọc hơn chương trình đệ quy. |
Tóm tắt - Đệ quy và Lặp lại
Bài viết này đã thảo luận về sự khác biệt giữa đệ quy và lặp. Cả hai đều có thể được sử dụng để giải quyết các vấn đề lập trình. Sự khác biệt giữa đệ quy và lặp là đệ quy là một cơ chế để gọi một hàm trong cùng một hàm và lặp đi lặp lại nó để thực hiện một tập lệnh lặp đi lặp lại cho đến khi điều kiện đã cho là đúng. Nếu một vấn đề có thể được giải quyết ở dạng đệ quy, nó cũng có thể được giải quyết bằng cách sử dụng lặp lại.
Tải xuống Phiên bản PDF của Đệ quy và Lặp lại
Bạn có thể tải xuống phiên bản PDF của bài viết này và sử dụng nó cho mục đích ngoại tuyến theo ghi chú trích dẫn. Vui lòng tải xuống phiên bản PDF tại đây Sự khác biệt giữa Đệ quy và Lặp lại
