Làm thế nào để đệ quy làm cho việc sử dụng bộ nhớ thời gian chạy không thể đoán trước?

Question

Trích dẫn từ Code Complete 2,

int Factorial(int number) { 
    if (number == 1) { 
     return 1; 
    } 
    else { 
     return number * Factorial(number - 1); 
    } 
} 

Ngoài việc là chậm^[1] và làm việc sử dụng bộ nhớ thời gian chạy không thể đoán trước^[2], phiên bản đệ quy của thói quen này khó khăn hơn để hiểu hơn phiên bản lặp lại, như sau:

int Factorial(int number) { 
    int intermediateResult = 1; 
    for (int factor = 2; factor <= number; factor++) { 
     intermediateResult = intermediateResult * factor; 
    } 
    return intermediateResult; 
} 

Tôi nghĩ phần chậm là do chi phí cuộc gọi hàm không cần thiết.

Nhưng làm cách nào để đệ quy sử dụng bộ nhớ thời gian chạy không thể đoán trước?

Chúng ta không thể dự đoán bao nhiêu bộ nhớ sẽ cần thiết (như chúng ta biết khi nào đệ quy được cho là kết thúc)? Tôi nghĩ rằng nó sẽ không thể dự đoán được như trường hợp lặp lại, nhưng không phải như vậy nữa.

Answer 1

Bởi vì các phương pháp đệ quy thực tế gọi chúng là bản thân nhiều lần, rất cần nhiều bộ nhớ ngăn xếp. Kể từ khi ngăn xếp được giới hạn, lỗi sẽ xảy ra nếu ngăn xếp ngăn xếp được vượt quá.

Answer 2

Nếu mức đệ quy trở nên quá sâu, bạn sẽ thổi ngăn xếp cuộc gọi và ăn nhiều bộ nhớ trong quá trình. Điều này có thể xảy ra nếu number của bạn là giá trị "đủ lớn". Bạn có thể làm tồi tệ hơn điều này? Có, nếu chức năng của bạn phân bổ nhiều đối tượng hơn với mọi cuộc gọi đệ quy.

Answer 3

Chúng ta không thể dự đoán được bao nhiêu bộ nhớ cần thiết (như chúng ta biết khi nào đệ quy được cho là kết thúc)? Tôi nghĩ rằng nó sẽ không thể dự đoán được như trường hợp lặp lại, nhưng không phải như vậy nữa.

Không, không phải trong trường hợp chung. Xem thảo luận về halting problem để biết thêm thông tin cơ bản. Bây giờ, đây là phiên bản đệ quy của một trong những vấn đề được đăng ở đó:

void u(int x) { 
    if (x != 1) { 
     u((x % 2 == 0) ? x/2 : 3*x+1); 
    } 
} 

Nó thậm chí còn có tính đệ quy đuôi. Vì bạn không thể dự đoán nếu điều này thậm chí sẽ chấm dứt bình thường, làm thế nào bạn có thể dự đoán bao nhiêu bộ nhớ là cần thiết?