DOUG LLOYD: Nếu bạn đã nhìn thấy video về đệ quy, toàn bộ quá trình có thể có dường như một chút huyền diệu. Làm thế nào nó hoạt động? Làm thế nào để các chức năng biết rằng họ cần phải chờ đợi cho giá trị khác để trở về từ một chức năng khác nhau gọi để có được kết quả chúng tôi muốn? Vâng, lý do công trình này là vì của cái gì được gọi là các cuộc gọi stack. Khi bạn gọi một hàm, hệ thống dành riêng không gian trong bộ nhớ cho chức năng đó để làm công việc của mình. Và chúng ta gọi là các khối của bộ nhớ đang được dành cho mỗi chức năng gọi một stack frame hay một khung chức năng. Và như bạn mong đợi, các khung stack sống trên một phần của ngăn xếp bộ nhớ. 

Nhiều hơn một chức năng stack frame có thể tồn tại trong bộ nhớ tại một thời gian nhất định. Nếu chính gọi là di chuyển chức năng, và di chuyển hướng cuộc gọi, cả ba chức năng có khung mở. Nhưng họ không phải tất cả có khung hoạt động. Các khung hình này được bố trí trong một chồng. Và khung từ Gần đây nhất được gọi là hàm luôn luôn là trên đỉnh của ngăn xếp. Và đó luôn là khung hoạt động. Chỉ có thực sự bao giờ một chức năng mà hoạt động tại một thời gian. Đó là một trong những ngày đầu của stack. 

Khi một cuộc gọi chức năng khác chức năng, nó loại nhấn pause. Nó loại là giữ lại, chờ đợi. Và một stack frame được đẩy vào ngăn xếp trên đầu trang của nó. Và đó trở thành khung hoạt động. Và khung ngay lập tức bên dưới nó cần phải chờ đợi cho đến khi nó là một lần nữa khung hoạt động trước khi nó có thể tiếp tục công việc của mình. Khi một chức năng là hoàn thành và hoàn thành công việc, khung của nó được popped ra khỏi stack. Đó là thuật ngữ. Và khung ngay lập tức dưới nó, như tôi vừa nói, trở thành các khung hoạt động mới. 

Và nếu nó gọi hàm khác, nó sẽ tạm dừng lại. Stack frame mà chức năng mới của sẽ được đẩy lên đỉnh của ngăn xếp. Nó sẽ làm công việc của mình. Nó có thể bật lại tắt. Và các chức năng khác dưới nó có thể tiếp tục một lần nữa. 

Vì vậy, hãy đi qua này một lần nữa, tìm lúc ý tưởng của các chức năng thừa mà chúng tôi xác định trong đệ quy video để xem chính xác cách thức kỳ diệu đằng sau này quá trình đệ quy được diễn ra. Vì vậy, đây là toàn bộ tập tin của chúng tôi, phải không? Chúng tôi định nghĩa hai functions-- chính và thực tế. Và như chúng ta có thể mong đợi, bất kỳ chương trình C sẽ để bắt đầu ở dòng đầu tiên của chính. 

Vì vậy, chúng ta tạo một stack frame mới cho chính. Và nó sẽ bắt đầu chạy. Cuộc gọi chính printf. Và printf sẽ in ra thừa của 5. Vâng, nó không biết những gì thừa của 5, và do đó, điều này gọi là đã tùy thuộc vào một cuộc gọi chức năng. Vì vậy, chính là sẽ tạm dừng ngay tại đó. Tôi sẽ rời khỏi nó mũi tên bên phải ở đó, màu sắc nó cùng một màu sắc như là ngăn xếp khung bên phải, để chỉ ra rằng chính sẽ đóng băng ở đây trong khi thừa của 5 được gọi. 

Vì vậy, giai thừa của 5 được gọi. Và nó sẽ bắt đầu ở rất bắt đầu của các chức năng thừa. Nó nhắc đi nhắc lại câu hỏi tôi bằng 1? 5 bằng 1? Ồ không. Vì vậy, nó sẽ đi xuống phần else return n lần thừa của n trừ đi 1. Tốt. 

Vì vậy, bây giờ, giai thừa của 5 tùy thuộc vào một cuộc gọi khác để factorial, đi qua trong 4 như các tham số. Và do đó, giai thừa của 5 khung hình, mà khung màu đỏ, sẽ đóng băng ngay tại đó tại dòng mà tôi đã chỉ ra và chờ cho thừa của 4 để kết thúc những gì nó cần phải làm như vậy mà sau đó nó có thể trở thành các khung hoạt động trở lại. 

Vì vậy factorial của 4 bắt đầu tại đầu thừa. Là 4 bằng 1? Không, vì vậy nó sẽ làm điều tương tự. Nó sẽ đi xuống các chi nhánh khác. Nó sẽ nhận được để mà dòng mã. OK, tôi sẽ trở lại bốn lần. Oh, thừa của 3-- vậy factorial của 4 phụ thuộc vào giai thừa của 3 hoàn thiện. 

Và do đó, nó cần gọi thừa của 3. Và điều đó sẽ đi qua cùng một quá trình một lần nữa. Nó bắt đầu thông qua, được ở đây. Thừa của 3 phụ thuộc về thừa của 1. Vì vậy, thừa của 2 bắt đầu, được ở đây. Nó phụ thuộc vào giai thừa của 1. Thừa của 1 bắt đầu. 

ĐƯỢC. Vì vậy, bây giờ, chúng tôi đang nhận một nơi nào đó thú vị, phải không? Vì vậy, bây giờ, 1 bằng 1. Và vì vậy chúng tôi trở về 1. Tại thời điểm này, chúng tôi đang quay trở lại. Các chức năng được thực hiện. Đó là thái độ is-- có không có gì khác cho nó để làm, và do đó, các khung stack cho thừa của 1 bật tắt. Mọi chuyện đã kết thúc rồi. Nó trở lại 1. Và bây giờ, thừa của 2, là khung ngay bên dưới nó trong ngăn xếp, trở thành khung hoạt động. 

Và nó có thể nhận chính xác nơi nó lại tắt. Nó được chờ đợi cho một giai thừa của 1 để kết thúc công việc của mình. Nó bây giờ đã hoàn thành. Và như vậy chúng ta ở đây. 

Thừa của 1 trả lại một giá trị là 1. Vì vậy, thừa của 2 lon nói trả lại 2 lần 1. Công việc của nó bây giờ được thực hiện. Nó thấy 2 để factorial 3, được chờ đợi nó. Thừa của 3 tại là khung trên, khung hoạt động trong stack. Và do đó, nó nói, OK, tốt, tôi sẽ để trở lại 3 lần 2, mà là 6. Và tôi sẽ cung cấp cho rằng đánh giá lại để thừa 4, đã được chờ đợi tôi. Tôi đa xong. Thừa của 3 bật ra khỏi ngăn xếp, và thừa của 4 doanh nghiệp là khung hoạt động. 

4 nói, OK, tôi sẽ trả lại 4 lần giai thừa của 3, đó là sáu. Đó là giá trị mà thừa của 3 trở lại. Và như vậy 4 lần 6 là 24. Và tôi sẽ vượt qua trở lại đó để factorial 5, đã được chờ đợi tôi. Thừa của 5 tại là khung hoạt động. Nó sẽ trả lại 5 lần thừa của 4-- 5 lần 24, hoặc 120-- và đưa ra giá trị đó trở lại chính, trong đó có được chờ đợi rất kiên nhẫn cho một thời gian dài ở dưới cùng của ngăn xếp. 

Đó là nơi mà nó bắt đầu. Nó làm cho cuộc gọi này. Một số khung đã qua ở đầu trang. Nó bây giờ đã trở lại trên đầu của stack. Đó là khung hoạt động. Vì vậy, chính có giá trị 120 trở lại từ giai thừa của 5. Nó được chờ đợi để in ra giá trị đó. Và sau đó nó được thực hiện. Không có nhiều dòng mã trong chính. Vì vậy, khung chính của bật tắt ngăn xếp, và chúng tôi đang thực hiện. 

Và đó là cách đệ quy trình. Đó là cách các khung stack làm việc. Những cuộc gọi chức năng đã xảy ra trước đó chỉ là về tạm dừng, chờ đợi cho các cuộc gọi tiếp theo để kết thúc để họ có thể trở thành hoạt động khung và hoàn thành những gì họ cần làm. 

Tôi Doug Lloyd. Đây là CS50.