Liên quan đến việc tái sử dụng ngăn xếp của một hàm gọi chính nó?

Question

nếu một hàm gọi chính nó trong khi xác định các biến cùng một lúc nó sẽ dẫn đến tràn ngăn xếp? Có bất kỳ tùy chọn nào trong gcc để sử dụng lại cùng một ngăn xếp hay không.

void funcnew(void) 
{ 
    int a=10; 
    int b=20; 
    funcnew(); 
    return ; 
} 

một chức năng có thể sử dụng lại khung ngăn xếp được sử dụng trước đó không? Tùy chọn trong gcc để tái sử dụng cùng một khung trong đệ quy đuôi là gì?

Answer 1

Không, mỗi lần đệ quy là một khung ngăn xếp mới. Nếu đệ quy vô cùng sâu, thì ngăn xếp cần thiết cũng là vô hạn, do đó bạn sẽ bị tràn ngăn xếp.

Answer 2

Thậm chí không xác định thông số bạn sẽ nhận được luồng lưu trữ truy cập. Vì địa chỉ trả về cũng được đẩy lên ngăn xếp.

Đó là (tôi đã học được điều này gần đây) có thể trình biên dịch tối ưu hóa vòng lặp của bạn thành một đệ quy đuôi (làm cho ngăn xếp không phát triển chút nào). Link to tail recursion question on SO

Answer 3

Có. Xem

-foptimize-sibling-gọi

Optimize anh chị em và đuôi cuộc gọi đệ quy.

Được kích hoạt ở các cấp -O2, -O3, -Os.

Chức năng của bạn được biên dịch để:

funcstack: 
.LFB0: 
    .cfi_startproc 
    xorl %eax, %eax 
    jmp func 
    .cfi_endproc 

(lưu ý khi nhảy tới func)

Tái sử dụng các khung stack khi một kết thúc chức năng bởi một cuộc gọi - điều này bao gồm trong tính tổng quát đầy đủ của nó thao túng ngăn xếp để đặt các thông số tại vị trí chính xác và thay thế cuộc gọi hàm bằng cách nhảy đến đầu hàm - là một tối ưu hóa nổi tiếng được gọi là [i] yêu cầu xóa cuộc gọi đuôi [/ i]. Nó được bắt buộc bởi một số ngôn ngữ (sơ đồ ví dụ) cho các cuộc gọi đệ quy (một cuộc gọi đệ quy là cách tự nhiên để diễn tả một vòng lặp trong các ngôn ngữ này). Như đã nêu ở trên, gcc có tối ưu hóa được triển khai cho C, nhưng tôi không chắc trình biên dịch nào có nó, tôi sẽ không phụ thuộc vào nó cho mã di động. Và lưu ý rằng tôi không biết có giới hạn nào trên đó - tôi không chắc chắn rằng gcc sẽ thao tác ngăn xếp nếu các kiểu tham số khác nhau.

Answer 4

Có, trong một số trường hợp trình biên dịch có thể thực hiện một cái gì đó gọi là tối ưu hóa cuộc gọi đuôi . Bạn nên kiểm tra với hướng dẫn biên dịch của bạn. (AProgrammer dường như đã trích dẫn hướng dẫn GCC trong câu trả lời của mình.)

Đây là một tối ưu hóa cần thiết khi thực hiện cho các ngôn ngữ chức năng ví dụ, nơi mã như vậy xảy ra thường xuyên.

Answer 5

Bạn không thể bỏ đi toàn bộ khung ngăn xếp vì cần thiết cho địa chỉ trả lại. trừ khi bạn đang sử dụng đệ quy đuôi, và trình biên dịch của bạn đã tối ưu hóa nó thành một vòng lặp. Nhưng để hoàn toàn trung thực về mặt kỹ thuật, bạn có thể loại bỏ tất cả các biến trong khung bằng cách làm cho chúng tĩnh. Tuy nhiên, điều này gần như chắc chắn là không phải những gì bạn muốn làm, và bạn không nên làm điều đó mà không biết chính xác những gì bạn đang làm, mà như bạn đã phải đặt câu hỏi này, bạn không.

Answer 6

Như những người khác đã lưu ý, chỉ có thể nếu (1) trình biên dịch của bạn hỗ trợ tối ưu hóa cuộc gọi đuôi và (2) nếu chức năng của bạn đủ điều kiện để tối ưu hóa như vậy. Tối ưu hóa là sử dụng lại ngăn xếp hiện có và thực hiện một JMP (tức là, một GOTO trong lắp ráp) thay vì một CALL.

Thực tế, chức năng mẫu của bạn thực sự đủ điều kiện để tối ưu hóa như vậy. Lý do là điều cuối cùng mà chức năng của bạn làm trước khi trở về là tự gọi; nó không phải làm bất cứ điều gì sau cuộc gọi cuối cùng đến funcnew(). Tuy nhiên, chỉ một số trình biên dịch sẽ thực hiện tối ưu hóa như vậy. GCC, ví dụ, sẽ làm điều đó. Để biết thêm thông tin, hãy xem Which, if any, C++ compilers do tail-recursion optimization?

Tài liệu cổ điển về điều này là chức năng giai thừa. Hãy tạo một hàm giai thừa đệ quy là không đủ điều kiện để tối ưu hóa cuộc gọi đuôi (TCO).

int fact(int n) 
{ 
    if (n == 1) return 1; 
    return n*fact(n-1); 
} 

Điều cuối cùng cần làm là nhân sốvới kết quả từ fact(n-1). Bằng cách nào đó loại bỏ hoạt động cuối cùng này, chúng tôi sẽ có thể tái sử dụng ngăn xếp. Hãy giới thiệu một biến ắc mà sẽ tính toán câu trả lời cho chúng ta:

int fact_helper(int n, int acc) 
{ 
    if (n == 1) return acc; 
    return fact_helper(n-1, n*acc); 
} 

int fact_acc(int n) 
{ 
    return fact_helper(n, 1); 
} 

Chức năng fact_helper làm việc, trong khi fact_acc chỉ là một chức năng thuận tiện để khởi tạo biến accumulator.

Lưu ý cách điều mới nhất fact_helper thực hiện là tự gọi. CALL này có thể được chuyển đổi thành JMP bằng cách tái sử dụng ngăn xếp hiện có cho các biến.

Với GCC, bạn có thể xác minh rằng nó được tối ưu hóa để một bước nhảy bằng cách nhìn vào lắp ráp tạo ra, ví dụ :

... 
    37     L12: 
    38 0040 0FAFC2    imull %edx, %eax 
    39 0043 83EA01    subl $1, %edx 
    40 0046 83FA01    cmpl $1, %edx 
    41 0049 75F5     jne  L12 
    ... 

Một số ngôn ngữ lập trình, chẳng hạn như Scheme, trên thực tế sẽ đảm bảo rằng việc triển khai thích hợp sẽ thực hiện tối ưu hóa như vậy. Họ thậm chí sẽ làm điều đó cho các cuộc gọi đuôi không đệ quy.