Hàm đệ quy này giải đố tôi, chuyện gì đang xảy ra?

Question

Tôi đã chơi xung quanh với đệ quy và đã làm chức năng đơn giản này. Tôi đã giả định rằng nó sẽ in ra 9-0 để stdout, nhưng, nó in 0-9. Tôi không thể thấy điều đó xảy ra chút nào.

int main() 
{ 
     rec(10); 
     return 0; 
} 

int rec(int n){ 
     if(n > 0) 
       printf("%d\n", rec(n -1)); 
     return n; 
} 

Answer 1

Như Michael Burr cho biết trong các ý kiến, nếu bạn muốn xem những gì đang xảy ra, biên dịch với các biểu tượng gỡ lỗi được kích hoạt, như thế này:

gcc -o test -g test.c 

Sau đó chạy với gdb như vậy.

gdb test 

Sau đó, để bắt đầu điều đang xảy ra, gõ

start 

nào phá vỡ tại cuộc gọi đầu tiên trong hàm main. Nhập

step 

để đến dòng tiếp theo trong mã và sau đó nhấn enter để tiếp tục lặp lại lệnh cuối cùng. Nếu bạn hài lòng, hãy nhập continue để dừng bước. Bạn sẽ thấy các giá trị và các dòng được đánh giá ở từng giai đoạn sẽ xác nhận các câu trả lời ở trên.

Hy vọng rằng sẽ cung cấp một số thông tin hữu ích.

Answer 2

Các rec chức năng trên dòng printf được đánh giá trước printf riêng của mình. Do đó, sâu nhất phiên bản của hàm rec được in trước tiên.

Answer 3

Hãy nghĩ về nó như thế này.

rec(10) 
rec(9) 
rec(8) 
rec(7) 
rec(6) 
rec(5) 
rec(4) 
rec(3) 
rec(2) 
rec(1) 
rec(0) 

Bắt đầu Tháo cuộn

printf("%d\n", 0); 
printf("%d\n", 1); 
printf("%d\n", 2); 
printf("%d\n", 3); 
printf("%d\n", 4); 
printf("%d\n", 5); 
printf("%d\n", 6); 
printf("%d\n", 7); 
printf("%d\n", 8); 
printf("%d\n", 9); 

Answer 4

Hãy viết lại mã của bạn như thế này:

int rec(int n){ 
     if(n > 0) 
     { 
       int retval = rec(n -1); 
       printf("%d\n", retval); 
     } 
     return n; 
} 

Liệu nó làm cho nó rõ ràng lý do tại sao 0 in đầu tiên trước 9?

Answer 5

Vì bạn đang tạo 9 môi trường 9 > 8 > 7 > 6 > 5 > 4> 3 > 2 > 1 > 0, giờ đây các môi trường này được xử lý giống như vậy sẽ là a(b(c(d(e(f(g())))))), đi từ điểm sâu nhất đến điểm đầu tiên.

Hãy nhớ rằng khi bạn làm điều này printf("%d",n(m)); bạn thực sự không in bất cứ điều gì, bạn đang nói "in kết quả của n (m)" sau đó khi nó cố gắng giải quyết n (m) bạn đang gọi một bản in khác và nói một lần nữa "giải quyết n (m-1)".

Bây giờ, khi bạn đạt đến n (0) nó sẽ trở về 0 để được in bởi các cuộc gọi cuối cùng của printf, do đó nó in 0 thì 1 .. 9.

Answer 6

int main() 
{ 
     rec(10); 
     return 0; 
} 

int rec(int n){ 
     if(n > 0) 
       printf("%d\n", rec(n -1)); 
     return n; 
} 

Nói chung, hãy xem xét một số mảnh của mã. Chúng tôi nói rằng có một mối quan hệ trực tiếp giữa các giải pháp lặp lại và đệ quy sao cho bất kỳ giải pháp nào có thể được viết lặp lại và ngược lại. Tuy nhiên, trong một số trường hợp, nó được coi là dễ dàng hơn để thể hiện một thuật toán đệ quy (ví dụ như Tháp Hà Nội.) Trong trường hợp mã trên tương đương sẽ là cấu trúc vòng lặp for.

này có thể được thực hiện như một chức năng như sau:

void _for(int i, int n) 
{ 
    if(i >= n) return; // TERMINAL<br /> 
    // some expression (ie. printf("%d\n",i);)<br /> 
    _for(i+1,n) // RECURSION<br /> 
} 

Lưu ý, điều này có thể được gia hạn sử dụng con trỏ hàm.