Stack overflow do chức năng đệ quy

Question

Là người mới bắt đầu với lập trình C++ và kiến ​​trúc hệ thống máy tính, tôi vẫn đang học những điều cơ bản về C++. Hôm qua tôi đọc về hàm đệ quy, vì vậy tôi quyết định viết của riêng tôi, đây là những gì tôi đã viết: (rất cơ bản)

int returnZero(int anyNumber) { 
    if(anyNumber == 0) 
     return 0; 
    else { 
     anyNumber--; 
     return returnZero(anyNumber); 
    } 

}

Và khi tôi làm điều này: int zero1 = returnZero (4793); nó gây ra một tràn ngăn xếp, tuy nhiên, nếu tôi vượt qua giá trị 4792 như tham số, không có tràn xảy ra.

Bất kỳ ý tưởng nào về lý do tại sao?

Answer 1

Bạn chỉ cần nhấn giới hạn kích thước của ngăn xếp cuộc gọi của hệ thống của bạn, đó là những gì đang xảy ra. Đối với một số lý do ngăn xếp trong hệ thống của bạn là nhỏ, độ sâu của 4793 cuộc gọi chức năng là khá nhỏ.

Answer 2

Bất cứ khi nào bạn gọi một hàm, bao gồm đệ quy, địa chỉ trả về và thường đối số được đẩy lên call stack. Ngăn xếp là hữu hạn, vì vậy nếu đệ quy quá sâu, cuối cùng bạn sẽ chạy ra khỏi không gian ngăn xếp.

Điều khiến tôi ngạc nhiên là chỉ mất 4793 cuộc gọi trên máy của bạn để làm tràn ngăn xếp. Đây là một ngăn xếp khá nhỏ. Bằng cách so sánh, chạy cùng một mã trên máy tính của tôi yêu cầu ~ 100x nhiều cuộc gọi trước khi chương trình bị treo.

Kích thước của ngăn xếp có thể định cấu hình. Trên Unix, lệnh là ulimit -s.

Cho rằng chức năng là tail-recursive, một số trình biên dịch có thể tối ưu hóa cuộc gọi đệ quy bằng cách biến nó thành bước nhảy. Một số trình biên dịch có thể lấy một ví dụ của bạn hơn nữa: khi được hỏi cho việc tối ưu tối đa, gcc 4.7.2 biến đổi toàn bộ chức năng thành:

int returnZero(int anyNumber) { 
    return 0; 
} 

Điều này đòi hỏi chính xác hai hướng dẫn lắp ráp:

_returnZero: 
     xorl %eax, %eax 
     ret 

Khá gọn gàng.

Answer 3

Ngăn xếp của bạn bị giới hạn về kích thước và do đó khi bạn thực hiện 4793 cuộc gọi, bạn đang đạt đến giới hạn trong khi 4792 chỉ đến trong. Mỗi cuộc gọi chức năng sẽ sử dụng một số không gian trên ngăn xếp để giữ nhà và có thể tranh luận.

Trang này cung cấp example về hình thức của một chồng trong khi gọi hàm đệ quy.

Answer 4

Tôi đoán là bạn có đủ chính xác đủ lớn để phù hợp với 4792 mục - hôm nay. Ngày mai hoặc ngày tiếp theo, con số đó có thể khác. Lập trình đệ quy có thể nguy hiểm và ví dụ này không hiểu tại sao. Chúng tôi cố gắng không để cho đệ quy nhận được điều này sâu hoặc 'xấu' có thể xảy ra.

Answer 5

Bất kỳ đệ quy "vô hạn" nào, đó là các cuộc gọi đệ quy không giới hạn tự nhiên đối với một số nhỏ (ish) sẽ có hiệu ứng này. Chính xác nơi giới hạn đi phụ thuộc vào hệ điều hành, môi trường chức năng được gọi trong (trình biên dịch, mà chức năng gọi hàm đệ quy, vv, vv).

Nếu bạn thêm biến khác, hãy nói int x[10]; cho hàm của bạn gọi hàm đệ quy của bạn, số cần thiết để sụp đổ nó sẽ thay đổi (có thể khoảng 5 hoặc hơn).

Biên dịch với trình biên dịch khác (hoặc thậm chí các cài đặt trình biên dịch khác, ví dụ: bật tối ưu hóa) và có thể sẽ thay đổi lại.

Answer 6

Sử dụng đệ quy, bạn có thể đạt SuperDigit:

public class SuperDigit 
{ 
    static int sum = 0; 

    int main() 
    { 
     int n = 8596854; 
     cout<<getSum(n); 
    } 

    int getSum(int n){ 
     sum=0; 
     while (n > 0) { 
      int rem; 
      rem = n % 10; 
      sum = sum + rem; 
      n = n/10; 
      getSum(n); 
     } 
     return sum; 
    } 
}