Có giới hạn cứng nào về độ sâu đệ quy trong C

Question

Chương trình đang thảo luận cố gắng tính sum-of-first-n-natural-numbers sử dụng recursion. Tôi biết điều này có thể được thực hiện bằng cách sử dụng một công thức đơn giản n*(n+1)/2 nhưng ý tưởng ở đây là sử dụng recursion. chương trình

là như sau: Chương trình

#include <stdio.h> 

unsigned long int add(unsigned long int n) 
{ 
    return (n == 0) ? 0 : n + add(n-1); 
} 

int main() 
{ 
    printf("result : %lu \n", add(1000000)); 
    return 0; 
} 

Các làm việc tốt cho n = 100,000 nhưng khi giá trị của n được tăng lên 1,000,000 nó dẫn đến một Segmentation fault (core dumped)

Sau đây được lấy từ thông điệp gdb .

Program received signal SIGSEGV, Segmentation fault. 
0x00000000004004cc in add (n=Cannot access memory at address 0x7fffff7feff8 
) at k.c:4 

Câu hỏi của tôi (s):

1. Có bất kỳ giới hạn cứng có dây vào recursion depth trong C? hoặc không recursion depth phụ thuộc vào bộ nhớ ngăn xếp có sẵn?

2. Lý do có thể khiến một chương trình nhận được tín hiệu reSIGSEGV là gì?

Answer 1

Nói chung giới hạn sẽ là kích thước của ngăn xếp. Mỗi lần bạn gọi một hàm, một lượng ngăn xếp nhất định sẽ được ăn (thường phụ thuộc vào hàm). Số lượng ăn là khung ngăn xếp, và nó được phục hồi khi hàm trả về. Kích thước ngăn xếp gần như là cố định khi chương trình bắt đầu, hoặc do được chỉ định bởi hệ điều hành (và thường có thể điều chỉnh ở đó), hoặc thậm chí được mã hóa cứng trong chương trình.

• Một số triển khai có thể có kỹ thuật để phân bổ phân đoạn ngăn xếp mới trong thời gian chạy. Nhưng nói chung, họ không.

• Một số chức năng sẽ tiêu thụ ngăn xếp theo những cách hơi khó lường hơn, chẳng hạn như khi chúng phân bổ mảng có độ dài thay đổi tại đó.

• Một số chức năng có thể được biên dịch để sử dụng các cuộc gọi đuôi theo cách sẽ bảo toàn không gian ngăn xếp. Đôi khi bạn có thể viết lại hàm của bạn để tất cả các cuộc gọi (ví dụ như chính nó) xảy ra như là điều cuối cùng nó làm, và mong đợi trình biên dịch của bạn để tối ưu hóa nó.

Không dễ để biết chính xác cần bao nhiêu không gian ngăn cho mỗi cuộc gọi đến một hàm và tùy thuộc vào mức tối ưu của trình biên dịch.Một cách rẻ tiền để làm điều đó trong trường hợp của bạn sẽ là in &n mỗi lần được gọi; n có khả năng sẽ nằm trên ngăn xếp (đặc biệt vì người cần phải lấy địa chỉ của nó - nếu không nó có thể nằm trong sổ đăng ký) và khoảng cách giữa các vị trí kế tiếp sẽ cho biết kích thước của khung ngăn xếp.

Answer 2

Không có giới hạn lý thuyết về độ sâu đệ quy trong C. Giới hạn duy nhất là giới hạn duy nhất của bạn trong thực thi, thường giới hạn không gian ngăn xếp.
(Lưu ý rằng tiêu chuẩn C không thực sự yêu cầu triển khai dựa trên ngăn xếp. Tôi không biết bất kỳ triển khai thực tế nào không dựa trên nền tảng, nhưng hãy ghi nhớ điều đó.)

A SIGSEGV có thể được gây ra bởi bất kỳ số lượng của sự vật, nhưng vượt quá giới hạn stack của bạn là một trong những tương đối phổ biến. Dereferencing một con trỏ xấu là một con trỏ khác.

Answer 3

Chuẩn C không xác định độ sâu được hỗ trợ tối thiểu cho các cuộc gọi chức năng. Nếu nó đã làm, mà là khá khó để đảm bảo anyway, nó sẽ có nó đề cập đến một nơi nào đó trong phần 5.2.4 Environmental limits.

Answer 4

1) Tiêu thụ ngăn xếp dự kiến ​​sẽ được giảm và được viết là tối ưu hóa đệ quy đuôi.

gcc-O3 prog.c

#include <stdio.h> 

unsigned long long int add(unsigned long int n, unsigned long long int sum){ 
    return (n == 0) ? sum : add(n-1, n+sum); //tail recursion form 
} 

int main(){ 
    printf("result : %llu \n", add(1000000, 0));//OK 
    return 0; 
}