Sự khác biệt giữa đệ quy và lặp

Sự khác biệt chính - Đệ quy lặp đi lặp lại
 

Đệ quy và lặp 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 lại phụ thuộc vào cách giải quyết vấn đề. Các 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 lặp lại là thực thi một tập lệnh liên tục cho đến khi điều kiện đã cho là đúng. Đệ quy và lặp là các kỹ thuật chính để phát triển thuật toán và xây dựng các ứng dụng phần mềm.

NỘI DUNG

1. Tổng quan và sự khác biệt chính
2. Đệ quy là gì
3. Lặp lại là gì
4. Điểm tương đồng giữa đệ quy và lặp
5. So sánh cạnh nhau - Đệ quy so với lặp ở dạng bảng
6. Tóm tắt

Đệ 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ó một điều kiện chấm dứt. Đệ quy vô hạn không có điều kiện chấm dứt.

Đệ quy có thể được giải thích bằ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 mã dưới đây để tính giai thừa của 3 (3! = 3 * 2 * 1).

intmain ()

int value = giai thừa (3);

printf (Fact Factorial là% d \ n, giá trị);

trả về 0;

intfactorial (intn)

if (n == 0)

trả lại 1;

khác

trả về n * giai 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). Sau đó 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 khối nếu khối điều kiện là điều kiện cơ sở. Theo Tương tự, chức năng giai thừa được gọi đi gọi lại.

Các hàm đệ quy có liên quan với ngăn xếp. Trong C, chương trình chính có thể có nhiều chức năng. Vì vậy, hàm 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 hàm được gọi, điều khiển được trao cho hàm được gọi. Sau khi thực hiện chức năng hoàn thành, điều khiển được trả về chính. 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 khung ngăn xếp để tiếp tục thực hiện.

Hình 01: Đệ quy

Trong chương trình trên, khi gọi giai thừa (3) từ chính, 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 đỉnh của ngăn xếp và cứ thế. 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 lần 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 đỉnh của ngăn xếp. Những khung stack có thể làm chậm tốc độ lên. 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ởi 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 thời gian là O (n).

Lặp lại là gì?

Lặp lại là một khối các hướng dẫn lặp đi lặp lại nhiều lần cho đến khi điều kiện đã cho là đúng. Lặp đi lặp lại có thể đạt được bằng cách sử dụng các vòng lặp cho các vòng lặp, các vòng lặp do, trong khi đó Cú pháp cho vòng lặp Cú pháp của cú pháp như sau.

for (khởi tạo; điều kiện; sửa đổi)

// các câu lệnh;

Hình 02: Sơ đồ dòng cho 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 thực thi. Những tuyên bố thực hiện cho đến khi điều kiện là đúng. Nếu điều kiện là sai, điều khiển sẽ chuyển sang câu lệnh tiếp theo sau vòng lặp cho vòng lặp. 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 sang 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, người hâm mộ đã lặp đi lặp lại.

Trong Tiếng Tây Ban Nha trong vòng lặp, 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ác câu lệnh

Trong vòng lặp do-do trực tiếp, điều kiện được kiểm tra ở cuối vòng lặp. Vì vậy, vòng lặp thực thi ít nhất một lần.

làm

//các 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 cách sử dụng phép lặp (xóa cho vòng lặp) như sau.

int chính ()

intn = 3, giai thừa = 1;

inti;

cho (i = 1; i<=n ; i++)

giai thừa = giai thừa * i;

printf (Fact Factorial là% d \ n, yếu tố);

trả về 0;

Điểm giống nhau giữa đệ quy và lặp?

• Cả hai đều là kỹ thuật để giải quyết vấn đề.
• Nhiệm vụ có thể được giải quyết trong đệ quy hoặc lặp.

Sự khác biệt giữa đệ quy và lặp?

Đệ quy vs Lặp lại
Đệ quy là một phương thức gọi một hàm trong cùng một hàm.	Lặp lại là một khối các hướng dẫn lặp đi lặp lại cho đến khi điều kiện đã cho là đúng.
Không gian phức tạp
Độ phức tạp không gian của các chương trình đệ quy cao hơn các lần lặp.	Độ phức tạp không gian thấp hơn trong các lần lặp.
Tốc độ
Thực hiện đệ quy chậm.	Thông thường, lặp lại nhanh hơn đệ quy.
Điều kiện
Nếu không có điều kiện chấm dứt, 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.
Cây rơm
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, ngăn xếp không được sử dụng.
Mã dễ đọc
Một 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 lặp đi 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 lại. Cả hai 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 lại nó để thực hiện một tập các 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 các lần lặp.

Tải xuống phiên bản PDF của đệ quy vs lặp

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

Tài liệu tham khảo:

1. Điểm, Hướng dẫn. Cơ sở dữ liệu cấu trúc dữ liệu và thuật toán đệ quy cơ bản. Cảnh, Điểm hướng dẫn, ngày 15 tháng 8 năm 2017. Có sẵn tại đây 
2. Công nghệ học. Recursion trong chức năng C | Hướng dẫn về ngôn ngữ C, YouTube, YouTube, ngày 12 tháng 9 năm 2016. Có sẵn tại đây  
3.yusuf lắc. Thuật toán đệ quy | Factorial - từng bước hướng dẫn YouTube YouTube, YouTube, ngày 14 tháng 10 năm 2013. Có sẵn tại đây  

Hình ảnh lịch sự:

1.'CPT-Recursion-Factorial-Code'By Pluke - Công việc riêng, (Miền công cộng) qua Commons Wikimedia 
2.'For-loop-chart'By Không có tác giả nào có thể đọc được trên máy - Công việc riêng được giả định. (CC BY-SA 2.5) qua Commons Wikimedia