Đệ quy hay lặp lại?
Có một cú đánh hiệu suất nếu chúng ta sử dụng một vòng lặp thay vì đệ quy hoặc ngược lại trong các thuật toán mà cả hai có thể phục vụ cùng một mục đích? Ví dụ: Kiểm tra xem chuỗi đã cho có phải là một palindrom không. Tôi đã thấy nhiều lập trình viên sử dụng đệ quy như một phương tiện để thể hiện khi một thuật toán lặp đơn giản có thể phù hợp với hóa đơn. Trình biên dịch có vai trò quan trọng trong việc quyết định sử dụng cái gì?
Có thể là đệ quy sẽ đắt hơn, tùy thuộc vào chức năng đệ quy là đệ quy đuôi (dòng cuối cùng là cuộc gọi đệ quy). Đệ quy đuôi nên được trình biên dịch nhận ra và tối ưu hóa cho đối tác lặp của nó (trong khi duy trì triển khai rõ ràng, ngắn gọn mà bạn có trong mã của mình).
Tôi sẽ viết thuật toán theo cách có ý nghĩa nhất và rõ ràng nhất đối với người hút kém (có thể là chính bạn hoặc người khác) phải duy trì mã trong vài tháng hoặc vài năm. Nếu bạn gặp phải các vấn đề về hiệu năng, thì hãy lập hồ sơ mã của bạn, và sau đó và chỉ sau đó xem xét tối ưu hóa bằng cách chuyển sang triển khai lặp. Bạn có thể muốn xem xét ghi nhớ và lập trình động .
Vòng lặp có thể đạt được hiệu suất đạt được cho chương trình của bạn. Đệ quy có thể đạt được hiệu suất đạt được cho lập trình viên của bạn. Chọn cái nào quan trọng hơn trong tình huống của bạn!
So sánh đệ quy với phép lặp cũng giống như so sánh tuốc nơ vít đầu phillips với tuốc nơ vít đầu phẳng. Đối với hầu hết các phần bạn có thể loại bỏ bất kỳ vít đầu phillips nào bằng đầu phẳng, nhưng sẽ dễ dàng hơn nếu bạn sử dụng tuốc nơ vít được thiết kế cho vít đó phải không?
Một số thuật toán chỉ cho vay để đệ quy vì cách chúng được thiết kế (các chuỗi Fibonacci, đi qua một cấu trúc giống như cây, v.v.). Đệ quy làm cho thuật toán ngắn gọn và dễ hiểu hơn (do đó có thể chia sẻ và tái sử dụng).
Ngoài ra, một số thuật toán đệ quy sử dụng "Đánh giá lười biếng" giúp chúng hiệu quả hơn so với các anh em lặp đi lặp lại của chúng. Điều này có nghĩa là họ chỉ thực hiện các phép tính đắt tiền tại thời điểm họ cần chứ không phải mỗi lần vòng lặp chạy.
Điều đó là đủ để bạn bắt đầu. Tôi cũng sẽ đào một số bài báo và ví dụ cho bạn.
Liên kết 1: Haskel vs PHP (Đệ quy so với Lặp lại)
Dưới đây là một ví dụ trong đó lập trình viên phải xử lý một tập dữ liệu lớn bằng PHP. Anh ta cho thấy việc đối phó với Haskel dễ dàng như thế nào bằng cách sử dụng đệ quy, nhưng vì PHP không có cách nào dễ dàng để thực hiện cùng một phương thức, anh ta buộc phải sử dụng phép lặp để có kết quả.
http://blog.webspecies.co.uk/2011-05-31/lazy-ev Assessment-with-php.html
Liên kết 2: Làm chủ đệ quy
Hầu hết danh tiếng xấu của đệ quy đến từ chi phí cao và kém hiệu quả trong các ngôn ngữ bắt buộc. Tác giả của bài viết này nói về cách tối ưu hóa các thuật toán đệ quy để làm cho chúng nhanh hơn và hiệu quả hơn. Ông cũng tìm hiểu làm thế nào để chuyển đổi một vòng lặp truyền thống thành một hàm đệ quy và lợi ích của việc sử dụng đệ quy đuôi. Những lời kết thúc của anh ấy thực sự tóm tắt một số điểm chính của tôi, tôi nghĩ:
"lập trình đệ quy cung cấp cho lập trình viên một cách tổ chức mã tốt hơn theo cách vừa có thể duy trì vừa phù hợp về mặt logic."
Liên kết 3: Đệ quy có nhanh hơn lặp không? (Trả lời)
Đây là một liên kết đến một câu trả lời cho một câu hỏi stackoverflow tương tự như của bạn. Tác giả chỉ ra rằng rất nhiều điểm chuẩn liên quan đến đệ quy hoặc vòng lặp là ngôn ngữ rất cụ thể . Các ngôn ngữ bắt buộc thường nhanh hơn bằng cách sử dụng vòng lặp và chậm hơn với đệ quy và ngược lại cho các ngôn ngữ chức năng. Tôi đoán điểm chính cần rút ra từ liên kết này là rất khó để trả lời câu hỏi theo nghĩa bất khả tri/tình huống mù ngôn ngữ.
Đệ quy sẽ tốn kém hơn trong bộ nhớ, vì mỗi cuộc gọi đệ quy thường yêu cầu một địa chỉ bộ nhớ được đẩy lên ngăn xếp - để sau đó chương trình có thể quay lại điểm đó.
Tuy nhiên, có nhiều trường hợp trong đó đệ quy là tự nhiên và dễ đọc hơn rất nhiều so với các vòng lặp - như khi làm việc với cây. Trong những trường hợp này, tôi khuyên bạn nên bám vào đệ quy.
Thông thường, người ta sẽ mong đợi hình phạt hiệu suất nằm ở hướng khác. Các cuộc gọi đệ quy có thể dẫn đến việc xây dựng các khung ngăn xếp bổ sung; hình phạt cho việc này khác nhau. Ngoài ra, trong một số ngôn ngữ như Python (chính xác hơn, trong một số triển khai của một số ngôn ngữ ...), bạn có thể chạy vào giới hạn ngăn xếp khá dễ dàng cho các tác vụ bạn có thể chỉ định đệ quy, chẳng hạn như tìm giá trị tối đa trong một cấu trúc dữ liệu cây. Trong những trường hợp này, bạn thực sự muốn gắn bó với các vòng lặp.
Viết các hàm đệ quy tốt có thể giảm phần nào hiệu suất phạt, giả sử bạn có trình biên dịch tối ưu hóa thu hồi đuôi, v.v. (Cũng kiểm tra kỹ để đảm bảo rằng hàm thực sự là đệ quy đuôi --- đó là một trong những điều mà nhiều người mắc lỗi trên, bật.)
Ngoài các trường hợp "Cạnh" (tính toán hiệu năng cao, độ sâu đệ quy rất lớn, v.v.), tốt nhất nên áp dụng phương pháp thể hiện rõ nhất ý định của bạn, được thiết kế tốt và có thể duy trì. Tối ưu hóa chỉ sau khi xác định một nhu cầu.
Đệ quy tốt hơn lặp lại cho các vấn đề có thể được chia thành nhiề, các phần nhỏ hơn.
Ví dụ, để thực hiện thuật toán Fibonnaci đệ quy, bạn chia sợi (n) thành sợi (n-1) và sợi (n-2) và tính cả hai phần. Lặp lại chỉ cho phép bạn lặp đi lặp lại một chức năng duy nhất.
Tuy nhiên, Fibonacci thực sự là một ví dụ bị hỏng và tôi nghĩ rằng việc lặp lại thực sự hiệu quả hơn. Lưu ý rằng sợi (n) = sợi (n-1) + sợi (n-2) và sợi (n-1) = sợi (n-2) + sợi (n-3). sợi (n-1) được tính hai lần!
Một ví dụ tốt hơn là một thuật toán đệ quy cho một cây. Vấn đề phân tích nút cha có thể được chia thành nhiề các vấn đề nhỏ hơn về phân tích từng nút con. Không giống như ví dụ về Fibonacci, các vấn đề nhỏ hơn độc lập với nhau.
Vì vậy, yeah - đệ quy tốt hơn lặp đi lặp lại cho các vấn đề có thể được chia thành nhiều vấn đề tương tự, nhỏ hơn, độc lập, tương tự.
Hiệu suất của bạn giảm khi sử dụng đệ quy vì gọi một phương thức, trong bất kỳ ngôn ngữ nào, ngụ ý rất nhiều sự chuẩn bị: mã cuộc gọi gửi địa chỉ trả về, tham số cuộc gọi, một số thông tin ngữ cảnh khác như thanh ghi bộ xử lý có thể được lưu ở đâu đó và tại thời điểm trả về phương thức được gọi gửi một giá trị trả về sau đó được người gọi lấy ra và bất kỳ thông tin ngữ cảnh nào được lưu trước đó sẽ được khôi phục. hiệu suất khác nhau giữa cách tiếp cận lặp và đệ quy nằm ở thời gian các thao tác này thực hiện.
Từ quan điểm triển khai, bạn thực sự bắt đầu nhận thấy sự khác biệt khi thời gian xử lý bối cảnh cuộc gọi tương đương với thời gian cần thiết để phương thức của bạn thực thi. Nếu phương thức đệ quy của bạn mất nhiều thời gian hơn để thực thi thì phần quản lý ngữ cảnh gọi, hãy đi theo cách đệ quy vì mã thường dễ đọc và dễ hiểu hơn và bạn sẽ không nhận thấy mất hiệu năng. Nếu không đi lặp đi lặp lại vì lý do hiệu quả.
Tôi tin rằng đệ quy đuôi trong Java hiện chưa được tối ưu hóa. Các chi tiết được rắc khắp này thảo luận về LtU và các liên kết liên quan. Nó có thể là một tính năng trong phiên bản 7 sắp tới, nhưng rõ ràng nó có một số khó khăn nhất định khi kết hợp với Kiểm tra ngăn xếp vì một số khung nhất định sẽ bị thiếu. Kiểm tra ngăn xếp đã được sử dụng để triển khai mô hình bảo mật chi tiết của chúng kể từ Java 2.
Trong nhiều trường hợp, đệ quy nhanh hơn vì bộ nhớ đệm, giúp cải thiện hiệu suất. Ví dụ, đây là một phiên bản lặp của sắp xếp hợp nhất bằng cách sử dụng thói quen hợp nhất truyền thống. Nó sẽ chạy chậm hơn so với việc thực hiện đệ quy vì bộ nhớ đệm được cải thiện hiệu suất.
Lặp đi lặp lại
public static void sort(Comparable[] a)
{
int N = a.length;
aux = new Comparable[N];
for (int sz = 1; sz < N; sz = sz+sz)
for (int lo = 0; lo < N-sz; lo += sz+sz)
merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}
Thực hiện đệ quy
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid+1, hi);
merge(a, aux, lo, mid, hi);
}
Tái bút - đây là những gì đã được Giáo sư Kevin Wayne (Đại học Princeton) nói về khóa học về các thuật toán được trình bày trên Coursera.
Có nhiều trường hợp nó đưa ra một giải pháp tao nhã hơn nhiều so với phương pháp lặp, ví dụ phổ biến là truyền qua cây nhị phân, do đó không nhất thiết phải khó duy trì hơn. Nói chung, các phiên bản lặp thường nhanh hơn một chút (và trong quá trình tối ưu hóa cũng có thể thay thế phiên bản đệ quy), nhưng các phiên bản đệ quy đơn giản hơn để hiểu và thực hiện chính xác.
Đệ quy rất hữu ích là một số tình huống. Ví dụ, hãy xem xét mã để tìm giai thừa
int factorial ( int input )
{
int x, fact = 1;
for ( x = input; x > 1; x--)
fact *= x;
return fact;
}
Bây giờ hãy xem xét nó bằng cách sử dụng hàm đệ quy
int factorial ( int input )
{
if (input == 0)
{
return 1;
}
return input * factorial(input - 1);
}
Bằng cách quan sát hai điều này, chúng ta có thể thấy rằng đệ quy là dễ hiểu. Nhưng nếu nó không được sử dụng cẩn thận thì nó cũng có thể dễ bị lỗi. Giả sử nếu chúng ta bỏ lỡ if (input == 0), thì mã sẽ được thực thi trong một thời gian và kết thúc với thường là tràn ngăn xếp.
Nó phụ thuộc vào ngôn ngữ. Trong Java bạn nên sử dụng các vòng lặp. Ngôn ngữ chức năng tối ưu hóa đệ quy.
Sử dụng đệ quy, bạn phải chịu chi phí của một cuộc gọi hàm với mỗi "lần lặp", trong khi với một vòng lặp, điều duy nhất bạn thường phải trả là tăng/giảm. Vì vậy, nếu mã cho vòng lặp không phức tạp hơn nhiều so với mã cho giải pháp đệ quy, vòng lặp thường sẽ vượt trội hơn so với đệ quy.
Đệ quy và lặp lại phụ thuộc vào logic nghiệp vụ mà bạn muốn thực hiện, mặc dù trong hầu hết các trường hợp, nó có thể được sử dụng thay thế cho nhau. Hầu hết các nhà phát triển đi đệ quy vì nó dễ hiểu hơn.
Đệ quy đơn giản hơn (và do đó - cơ bản hơn) so với bất kỳ định nghĩa có thể có của phép lặp. Bạn có thể định nghĩa một hệ thống hoàn chỉnh Turing chỉ với một cặp tổ hợp (vâng, ngay cả bản thân đệ quy cũng là một khái niệm phái sinh trong một hệ thống như vậy). Lambda tính toán là một hệ thống cơ bản mạnh mẽ không kém, có các hàm đệ quy. Nhưng nếu bạn muốn xác định một lần lặp đúng, bạn cần bắt đầu nhiều hơn nữa.
Đối với mã - không, mã đệ quy trên thực tế dễ hiểu và dễ bảo trì hơn nhiều so với mã lặp hoàn toàn, vì hầu hết các cấu trúc dữ liệu đều được đệ quy. Tất nhiên, để làm cho đúng, người ta sẽ cần một ngôn ngữ với sự hỗ trợ cho các chức năng và đóng cửa bậc cao, ít nhất - để có được tất cả các tổ hợp và trình lặp chuẩn một cách gọn gàng. Tất nhiên, trong C++, các giải pháp đệ quy phức tạp có thể trông hơi xấu, trừ khi bạn là người dùng khó tính của FC++ và giống nhau.
Nếu bạn chỉ lặp đi lặp lại qua một danh sách, thì chắc chắn, lặp đi lặp lại.
Một vài câu trả lời khác đã đề cập đến việc đi ngang qua cây (chiều sâu trước). Nó thực sự là một ví dụ tuyệt vời, bởi vì đó là một điều rất phổ biến đối với cấu trúc dữ liệu rất phổ biến. Đệ quy là cực kỳ trực quan cho vấn đề này.
Kiểm tra các phương thức "tìm" tại đây: http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html
Tôi nghĩ rằng trong đệ quy (không đuôi) sẽ có một cú đánh hiệu năng để phân bổ một ngăn xếp mới, v.v ... mỗi khi hàm được gọi (tất nhiên phụ thuộc vào ngôn ngữ).
Trong C++ nếu hàm đệ quy là một templated, thì trình biên dịch có nhiều cơ hội để tối ưu hóa nó hơn, vì tất cả các kiểu khấu trừ và khởi tạo hàm sẽ xảy ra trong thời gian biên dịch. Trình biên dịch hiện đại cũng có thể nội tuyến chức năng nếu có thể. Vì vậy, nếu một người sử dụng các cờ tối ưu hóa như -O3 hoặc -O2 trong g++, thì việc thu hồi có thể có cơ hội nhanh hơn các lần lặp. Trong các mã lặp, trình biên dịch sẽ có ít cơ hội hơn để tối ưu hóa nó, vì nó đã ở trạng thái tối ưu ít nhiều (nếu được viết đủ tốt).
Trong trường hợp của tôi, tôi đã cố gắng thực hiện lũy thừa ma trận bằng cách bình phương bằng cách sử dụng các đối tượng ma trận Armadillo, theo cả cách đệ quy và lặp. Thuật toán có thể được tìm thấy ở đây ... https://en.wikipedia.org/wiki/Exponentiation_by_squared . Các chức năng của tôi đã được tạo khuôn mẫu và tôi đã tính 1,000,00012x12 ma trận được nâng lên thành sức mạnh 10. Tôi đã nhận được kết quả sau:
iterative + optimisation flag -O3 -> 2.79.. sec
recursive + optimisation flag -O3 -> 1.32.. sec
iterative + No-optimisation flag -> 2.83.. sec
recursive + No-optimisation flag -> 4.15.. sec
Những kết quả này đã thu được bằng cách sử dụng gcc-4.8 với cờ c ++ 11 (-std=c++11) và Armadillo 6.1 với Intel mkl. Trình biên dịch Intel cũng cho thấy kết quả tương tự.
Đệ quy? Tôi phải bắt đầu từ đâu, wiki sẽ cho bạn biết, đó là quá trình lặp lại các mục theo cách tự tương tự "
Ngày trước khi tôi đang làm C, đệ quy C++ là một vị thần gửi, đại loại như "Đệ quy đuôi". Bạn cũng sẽ tìm thấy nhiều thuật toán sắp xếp sử dụng đệ quy. Ví dụ sắp xếp nhanh: http://alienryderflex.com/quicksort/
Đệ quy giống như bất kỳ thuật toán nào khác hữu ích cho một vấn đề cụ thể. Có lẽ bạn có thể không tìm thấy việc sử dụng ngay lập tức hoặc thường xuyên nhưng sẽ có vấn đề bạn sẽ rất vui vì nó có sẵn.
nó phụ thuộc vào "độ sâu đệ quy". nó phụ thuộc vào mức độ chi phí của hàm gọi sẽ ảnh hưởng đến tổng thời gian thực hiện.
Ví dụ, tính toán giai thừa cổ điển theo cách đệ quy rất không hiệu quả do: - nguy cơ tràn dữ liệu - rủi ro tràn ngăn xếp - phí gọi hàm chiếm 80% thời gian thực hiện
trong khi phát triển thuật toán tối thiểu để phân tích vị trí trong trò chơi cờ vua sẽ phân tích các động tác N tiếp theo có thể được thực hiện theo đệ quy trên "độ sâu phân tích" (như tôi đang làm ^ _ ^)
Mike đúng. Đệ quy đuôi là không được tối ưu hóa bởi trình biên dịch Java hoặc JVM. Bạn sẽ luôn nhận được một ngăn xếp tràn với thứ gì đó như thế này:
int count(int i) {
return i >= 100000000 ? i : count(i+1);
}
Đệ quy có một nhược điểm là thuật toán mà bạn viết sử dụng đệ quy có độ phức tạp không gian O(n). Trong khi aproach lặp có độ phức tạp không gian là O (1). Đây là ưu điểm của việc sử dụng phép lặp trên đệ quy. Vậy thì tại sao chúng ta sử dụng đệ quy?
Xem bên dưới.
Đôi khi, việc viết một thuật toán bằng cách sử dụng đệ quy sẽ dễ dàng hơn trong khi viết thuật toán tương tự khó hơn một chút. Trong trường hợp này nếu bạn chọn thực hiện theo phương pháp lặp, bạn sẽ phải tự xử lý stack.
Bạn phải nhớ rằng sử dụng đệ quy quá sâu, bạn sẽ chạy vào Stack Overflow, tùy thuộc vào kích thước ngăn xếp được phép. Để ngăn chặn điều này, hãy đảm bảo cung cấp một số trường hợp cơ bản kết thúc đệ quy.
Theo tôi biết, Perl không tối ưu hóa các cuộc gọi đệ quy đuôi, nhưng bạn có thể giả mạo nó.
sub f{
my($l,$r) = @_;
if( $l >= $r ){
return $l;
} else {
# return f( $l+1, $r );
@_ = ( $l+1, $r );
goto &f;
}
}
Khi lần đầu tiên được gọi, nó sẽ phân bổ không gian trên ngăn xếp. Sau đó, nó sẽ thay đổi các đối số của nó và khởi động lại chương trình con, mà không cần thêm bất cứ điều gì nữa vào ngăn xếp. Do đó, nó sẽ giả vờ rằng nó không bao giờ tự gọi mình, thay đổi nó thành một quá trình lặp đi lặp lại.
Lưu ý rằng không có "my @_;" hoặc "local @_;", nếu bạn đã làm thì nó sẽ không còn hoạt động nữa.
Nếu các lần lặp là nguyên tử và các đơn đặt hàng có cường độ đắt hơn so với việc đẩy khung ngăn xếp mới và tạo một luồng mới và bạn có nhiều lõi và của bạn môi trường thời gian chạy có thể sử dụng tất cả chúng, sau đó một cách tiếp cận đệ quy có thể mang lại hiệu suất tăng rất lớn khi kết hợp với đa luồng. Nếu số lần lặp trung bình không thể dự đoán được thì có thể nên sử dụng nhóm luồng sẽ kiểm soát phân bổ luồng và ngăn quá trình của bạn tạo quá nhiều luồng và làm hỏng hệ thống.
Ví dụ, trong một số ngôn ngữ, có các triển khai sắp xếp hợp nhất đa luồng đệ quy.
Nhưng một lần nữa, đa luồng có thể được sử dụng với vòng lặp thay vì đệ quy, do đó, sự kết hợp này sẽ hoạt động tốt như thế nào phụ thuộc vào nhiều yếu tố bao gồm HĐH và cơ chế phân bổ luồng của nó.
Chỉ sử dụng Chrome 45.0.2454,85 m, đệ quy dường như là một số tiền Nice nhanh hơn.
Đây là mã:
(function recursionVsForLoop(global) {
"use strict";
// Perf test
function perfTest() {}
perfTest.prototype.do = function(ns, fn) {
console.time(ns);
fn();
console.timeEnd(ns);
};
// Recursion method
(function recur() {
var count = 0;
global.recurFn = function recurFn(fn, cycles) {
fn();
count = count + 1;
if (count !== cycles) recurFn(fn, cycles);
};
})();
// Looped method
function loopFn(fn, cycles) {
for (var i = 0; i < cycles; i++) {
fn();
}
}
// Tests
var curTest = new perfTest(),
testsToRun = 100;
curTest.do('recursion', function() {
recurFn(function() {
console.log('a recur run.');
}, testsToRun);
});
curTest.do('loop', function() {
loopFn(function() {
console.log('a loop run.');
}, testsToRun);
});
})(window);
KẾT QUẢ
// 100 chạy bằng cách sử dụng tiêu chuẩn cho vòng lặp
100x cho vòng lặp chạy. Thời gian hoàn thành: 7.683ms
// 100 chạy bằng cách sử dụng phương pháp đệ quy chức năng w/đệ quy đuôi
100x đệ quy chạy. Thời gian hoàn thành: 4.841ms
Trong ảnh chụp màn hình bên dưới, đệ quy lại chiến thắng với mức chênh lệch lớn hơn khi chạy ở 300 chu kỳ trên mỗi bài kiểm tra
