2012-12-31 20 views
18

Tôi đã được hiển thị một chương trình mẫu để chứng minh đệ quy có vẻ như nó không hoạt động nhưng thực hiện. Logic là khá rõ ràng nhưng tại sao nó hoạt động ngay cả khi các cuộc gọi chức năng đệ quy không được trả lại? Có vẻ như lệnh return thoát ra khỏi ngăn xếp ngay cả khi nó không được yêu cầu. Đây có phải là một tiêu chuẩn ngôn ngữ hay một điều gcc? Tôi đã thấy nó với C và C++ được biên dịch bằng gcc trên Windows và Linux.Tại sao một cuộc gọi trả lại bị từ chối thoát ra khỏi ngăn xếp mà không có câu lệnh trả về rõ ràng?

#include <iostream> 
#include <cstdlib> 

using namespace std; 

int isprime(int num, int i) 
{ 
    if (i == 1) { 
     return 1; 
    } 
    else { 
     if (num % i == 0) 
     return 0; 
     else 
     isprime(num, i-1); // should be returned 
    } 
} 


int main(int argc, char** argv) 
{ 
    int input = atoi(argv[1]); 
    cout << input << "\t" << isprime(input, input/2) << "\n"; 
} 
+12

Hành vi không xác định bao gồm mã đang hoạt động do tai nạn. Các cuộc gọi chức năng lá giá trị trả lại trong sổ đăng ký cpu phải. –

+2

Tôi không thấy lý do bỏ phiếu xuống câu hỏi. Đó là một nghi ngờ khá tốt nhiều người mới bắt đầu có thể có. – varevarao

+3

@varevarao: Người mới bắt đầu "nghi ngờ" hài lòng bởi nỗ lực nghiên cứu. Điều đó nói rằng, tôi upvoted. –

Trả lời

20

Những thứ như thế chỉ hoạt động nếu vô tình giá trị trả lại xảy ra trong sổ đăng ký nơi người gọi mong đợi nó. Điều này chỉ hoạt động nếu điều này được thực hiện bởi trình biên dịch của bạn như là một hàm đệ quy. Về mặt kỹ thuật hành vi không xác định để sử dụng giá trị trả lại của hàm không cung cấp.

Chỉnh sửa: Trên kiến ​​trúc hiện đại, giá trị trả về của hàm cho giá trị có thể được chuyển vào sổ đăng ký phần cứng cụ thể. Khi bạn gọi hàm của bạn đệ quy, ở dưới cùng trong mọi trường hợp thanh ghi phần cứng được đặt thành giá trị mong đợi. Nếu tình cờ khi xuất hiện từ đệ quy thì thanh ghi phần cứng không bao giờ thay đổi, bạn kết thúc với giá trị chính xác.

Tất cả mẫu này sẽ không hoạt động, nếu giá trị trả về sẽ được đặt ở một số vị trí của ngăn xếp của người gọi (đệ quy).

Trong mọi trường hợp, tất cả điều đó phải được ghi lại bởi bất kỳ trình biên dịch hiện đại nào và cung cấp cho bạn cảnh báo. Nếu không, bạn không có trình biên dịch tốt, hoặc bạn đang sử dụng các tùy chọn dòng lệnh quá phòng thủ.

Đêm trước năm mới đặc biệt: Trong thế giới thực, mã như thế này (với số return) thậm chí sẽ không được nhận dạng là hàm đệ quy. Với nỗ lực không quá nhiều bạn sẽ tìm thấy một biến thể lặp đi lặp lại của chức năng đó, và bất kỳ trình biên dịch hiện đại phong nha sẽ có thể tìm thấy nó là tốt nếu bạn yêu cầu tối ưu hóa tối đa.

+1

_giá trị trả về sẽ xảy ra trong sổ đăng ký nơi người gọi mong đợi nó._ Bạn có thể giải thích điều này một chút không? – varevarao

-3

Bạn không quên tuyên bố trả lại? Đối với đệ quy bình thường, bạn cần phải trả lại trước isprime(num,i-1);. Tôi đoán điều này thậm chí sẽ đưa ra một cảnh báo biên dịch nếu bạn biên dịch điều này bằng các quy tắc nghiêm ngặt, bởi vì hàm phải luôn trả về một int, bây giờ nó không (ít nhất là nếu trình biên dịch của bạn không sửa lỗi này).

+3

Đó chính xác là câu hỏi. Tôi nghĩ rằng nó sẽ đòi hỏi một tuyên bố trở lại nhưng nó không. – mmdanziger

+0

@mmdanziger Vâng, chỉ cần nhận ra điều đó. Tôi nghĩ rằng nếu điều này làm việc nó là hành vi không xác định như Jens giải thích. Biên dịch bằng cách sử dụng một số tùy chọn nghiêm ngặt và có thể bạn sẽ nhận được cảnh báo. – Aloys

+1

Biên dịch với g ++ -Wall sẽ cảnh báo "điều khiển đến hết chức năng không có giá trị" –

5

Rất nhiều ở đây phụ thuộc vào ý bạn của "nó hoạt động"?

để thử và trả lời điểm chính của câu hỏi của bạn, chức năng sẽ trở lại khi kết thúc chức năng, có hay không một câu lệnh trả về được đáp ứng.

Tôi hy vọng sẽ thấy cảnh báo trình biên dịch cho bạn biết các đường dẫn điều khiển có thể không trả lại giá trị, trong C++ ở mọi tốc độ. Kết quả trong hành vi chưa xác định, hãy xem câu hỏi này: not returning a value from a non-void returning function

Tôi sẽ nói ví dụ này "sau khi tìm được số nguyên tố và isPrime trả về, sau đó hàm tiếp theo lên ngăn xếp cũng được trả tự do. Không có gì phụ thuộc vào giá trị trả về của isPrime, vì vậy chương trình sẽ chạy sao lưu ngăn xếp và xuất ra một thứ gì đó.

... nhưng vì hành vi không xác định, giá trị thực sự được xuất có thể là rác. Nếu bạn đang nhìn thấy 0 & 1 phù hợp với số nguyên tố làm đầu vào, thì wow.

Nếu bạn nghĩ rằng điều này đang hoạt động, tôi sẽ xem xét thử nghiệm rộng rãi hơn với các giá trị khác nhau.

Bạn cũng đang xây dựng với bất kỳ cài đặt "gỡ lỗi" nào chưa? nếu như vậy hãy thử lại lần nữa với các thiết lập gỡ lỗi, như thiese đôi khi làm thêm công việc để giữ cho mọi thứ uninitialised bộ nhớ sạch sẽ.

2

tôi có thể giải thích chính xác những gì sẽ xảy ra:

Các hàm được gọi, và nó recurses trở lại vào bản thân cho đến khi nó đạt đến sự trở lại ở hai modulo (return 0) hoặc cuối của đệ quy (trở về 1). Tại thời điểm này, hàm reuturns cho người gọi, đó là is_prime. Nhưng không có thêm mã nào trong hàm để thực hiện, vì vậy nó ngay lập tức trả về mà không cần thêm bất kỳ hành động nào.

Tuy nhiên, bạn có thể dễ dàng phá vỡ điều này bằng cách, ví dụ: thêm printf("Done for %d, %d\n", num, i); sau lệnh gọi is_prime() [không phải nằm trong câu lệnh if]. Hoặc thêm một đối tượng C++ được tạo và phá hủy khi nhập/thoát của hàm, làm ví dụ khác.

Bạn thật may mắn khi nó hoạt động. Và nó rất dễ vỡ và dễ vỡ - biên dịch nó với một trình biên dịch khác (hoặc với các cài đặt tối ưu hóa khác nhau, hoặc một phiên bản mới của trình biên dịch, hoặc một triệu thứ khác), và nó cũng có thể phá vỡ.

Các vấn đề liên quan