[MUSIC CHƠI] 

DOUG LLOYD: Bạn có thể nghĩ rằng mã chỉ được sử dụng để thực hiện một nhiệm vụ. Bạn viết nó ra. Nó làm điều gì đó. Đó là khá nhiều đó. 

Bạn biên dịch nó. Bạn chạy chương trình. Bạn tốt để đi. 

Nhưng tin hay không, nếu bạn mã trong một thời gian dài, bạn thực sự có thể đến để xem mã như một cái gì đó là đẹp. Nó giải quyết một vấn đề trong một cách rất thú vị, hay đó chỉ là một cái gì đó thực sự gọn về hình thức của nó. Bạn có thể cười vào tôi, nhưng đó là sự thật. Và đệ quy là một trong những cách để loại có được ý tưởng này xinh đẹp, thanh lịch, tìm kiếm mã. Nó giải quyết vấn đề theo cách mà là thú vị, dễ dàng để hình dung, và đáng ngạc nhiên ngắn. 

Các tác phẩm theo cách đệ quy là một hàm đệ quy được định nghĩa như là một chức năng mà các cuộc gọi nó như một phần thực thi của nó. Điều đó có vẻ hơi lạ, và chúng ta sẽ thấy một chút về cách làm việc này trong một thời điểm. Nhưng một lần nữa, các thủ tục đệ quy là sẽ rất thanh lịch bởi vì họ đang đi để giải quyết vấn đề này mà không có có tất cả các chức năng khác hoặc những vòng dài. Bạn sẽ thấy rằng những đệ quy thủ tục sẽ xem xét quá ngắn. Và họ thực sự sẽ làm cho mã của bạn trông rất xinh đẹp hơn. 

Tôi sẽ cung cấp cho bạn một ví dụ điều này để xem như thế nào một thủ tục đệ quy có thể được xác định. Vì vậy, nếu bạn đã quen thuộc với điều này từ lớp toán nhiều năm trước đây, có của một cái gì đó gọi là chức năng thừa, mà thường là ký hiệu là một dấu chấm than, mà được xác định trên tất cả các số nguyên dương. Và cách mà n thừa được tính là bạn nhân tất cả các con số nhỏ hơn hoặc bằng n together-- tất cả các số nguyên ít hơn hoặc bằng n với nhau. 

Vì vậy, 5 giai thừa là 5 lần 4 lần 3 lần 2 lần 1. Và 4 giai thừa là 4 lần 3 lần 2 lần 1 và như vậy. Bạn nhận được các ý tưởng. 

Khi lập trình, chúng tôi không sử dụng n, dấu chấm than. Vì vậy, chúng tôi sẽ xác định các nhân tố chức năng là thực tế của n. Và chúng ta sẽ sử dụng để tạo ra giai thừa một giải pháp đệ quy cho một vấn đề. Và tôi nghĩ rằng bạn có thể tìm thấy rằng nó rất nhiều trực quan hơn hấp dẫn hơn so với lặp đi lặp lại phiên bản này, mà chúng tôi cũng sẽ có một cái nhìn tại trong một thời điểm. 

Vì vậy, đây là một vài pun facts-- intended-- về các factorial-- chức năng thừa. Giai thừa của 1, như tôi đã nói, là 1. Giai thừa của 2 là 2 lần 1. Giai thừa của 3 là 3 lần 2 lần 1, và như vậy. Chúng tôi nói chuyện về 4 và 5 đã. 

Nhưng nhìn vào điều này, không phải là điều này có đúng? Không factorial của 2 chỉ 2 lần giai thừa của 1? Ý tôi là, giai thừa của 1 là 1. Vậy tại sao chúng ta không thể nói rằng, kể từ khi thừa của 2 là 2 lần 1, nó thực sự chỉ là 2 lần giai thừa của 1? 

Và sau đó mở rộng ý tưởng đó, không phải là giai thừa của 3 chỉ 3 lần giai thừa của 2? Và giai thừa của 4 là 4 lần giai thừa của 3, và như vậy? Trong thực tế, giai thừa của bất kỳ số có thể chỉ được thể hiện nếu chúng ta loại của tiến hành việc này mãi mãi. Chúng ta có thể loại khái quát vấn đề thừa vì nó là n lần thừa của n trừ đi 1. Đó là n lần sản phẩm của tất cả các con số nhỏ hơn tôi. 

Ý tưởng này, điều này khái quát của vấn đề, cho phép chúng tôi để đệ quy xác định các chức năng thừa. Khi bạn định nghĩa một hàm đệ quy, có hai điều đó cần phải là một phần của nó. Bạn cần phải có một cái gì đó gọi là một trường hợp cơ sở, trong đó, khi bạn kích hoạt nó, sẽ ngăn chặn quá trình đệ quy. 

Nếu không, một chức năng mà các cuộc gọi itself-- như bạn có thể imagine-- thể đi mãi mãi. Chức năng gọi hàm kêu gọi các cuộc gọi chức năng chức năng cuộc gọi chức năng. Nếu bạn không có một cách để ngăn chặn nó, chương trình của bạn sẽ bị mắc kẹt một cách hiệu quả tại một vòng lặp vô hạn. Nó sẽ sụp đổ cuối cùng, bởi vì nó sẽ chạy ra khỏi bộ nhớ. Nhưng đó là bên cạnh điểm. 

Chúng tôi cần phải có một số cách khác để ngăn chặn thứ bên cạnh chương trình rơi của chúng tôi, vì một chương trình mà treo là có lẽ không đẹp hoặc thanh lịch. Và vì vậy chúng tôi gọi đây là trường hợp cơ sở. Đây là một giải pháp đơn giản cho một vấn đề mà dừng lại quá trình đệ quy từ xảy ra. Vì vậy, đó là một phần của một hàm đệ quy. 

Phần thứ hai là trường hợp đệ quy. Và đây là nơi mà các đệ quy sẽ thực sự diễn ra. Đây là nơi mà các chức năng sẽ gọi chính nó. 

Nó sẽ không gọi chính nó trong một cách chính xác giống như cách nó đã được gọi. Nó sẽ là một biến thể nhẹ mà làm cho các vấn đề đó cố gắng để giải quyết một chút teeny nhỏ hơn. Nhưng nó thường đi buck giải quyết phần lớn các giải pháp một cuộc gọi khác nhau xuống dòng. 

Mà của những vẻ giống như trường hợp cơ sở ở đây? Mà một trong những vẻ như Giải pháp đơn giản nhất để một vấn đề? Chúng tôi có một loạt các giai thừa, và chúng tôi có thể tiếp tục đi on-- 6, 7, 8, 9, 10, và như vậy. 

Nhưng một trong những trông giống như một trường hợp tốt để được các trường hợp cơ sở. Đó là một giải pháp rất đơn giản. Chúng tôi không cần phải làm bất cứ điều gì đặc biệt. 

Giai thừa của 1 chỉ 1 là. Chúng tôi không phải làm bất kỳ nhân ở tất cả. Nó có vẻ như nếu chúng ta đang đi để thử và giải quyết vấn đề này, và chúng ta cần phải ngăn chặn đệ quy một nơi nào đó, có lẽ chúng ta muốn dừng lại nó khi chúng tôi nhận được 1. Chúng tôi không muốn dừng lại trước đó. 

Vì vậy, nếu chúng ta đang xác định chức năng thừa của chúng tôi, đây là một bộ xương cho làm thế nào chúng ta có thể làm điều đó. Chúng tôi cần phải cắm vào hai things-- trường hợp cơ sở và các trường hợp đệ quy. Trường hợp cơ sở là gì? Nếu n là bằng 1, trở 1-- đó một vấn đề thực sự đơn giản để giải quyết. 

Giai thừa của 1 là 1. Nó không phải 1 lần bất cứ điều gì. Nó chỉ là 1. Đó là một thực tế rất dễ dàng. Và đó có thể là trường hợp cơ sở của chúng tôi. Nếu chúng ta có được thông qua 1 thành này chức năng, chúng tôi sẽ chỉ trả lại 1. 

Các đệ quy là gì trường hợp có thể trông như thế nào? Đối với tất cả các số khác bên cạnh 1, mô hình là những gì? Vâng, nếu chúng ta đang dùng giai thừa của n, đó là lần n giai thừa của n trừ đi 1. 

Nếu chúng ta lấy thừa của 3, đó là 3 lần giai thừa của 3 trừ đi 1, hoặc 2. Và do đó, nếu chúng ta không nhìn vào 1, nếu không return n lần thừa của n trừ đi 1. Nó khá dễ hiểu. 

Và vì lợi ích của việc có một chút sạch và mã thanh lịch hơn, biết rằng nếu chúng ta có vòng single-line hoặc đơn dòng nhánh có điều kiện, chúng ta có thể thoát khỏi tất cả các dấu ngoặc nhọn xung quanh họ. Vì vậy, chúng ta có thể hợp nhất này để này. Điều này có chính xác như nhau chức năng như thế này. 

Tôi chỉ lấy đi những xoăn niềng răng, bởi vì chỉ có một dòng bên trong của những nhánh có điều kiện. Vì vậy, những cư xử hệt. Nếu n là bằng 1, trở về 1. Nếu không trả lại n lần giai thừa của n trừ đi 1. Vì vậy, chúng tôi đang làm cho vấn đề nhỏ hơn. Nếu n bắt đầu ra như là 5, chúng ta sẽ trả lại 5 lần thừa của 4. Và chúng ta sẽ thấy trong một phút khi chúng tôi nói chuyện về stack-- cuộc gọi trong một video khác nơi chúng ta nói về gọi stack-- chúng ta sẽ tìm hiểu về lý do tại sao chính xác quá trình này hoạt động. 

Nhưng trong khi thừa của 5 nói trả lại 5 lần thừa của 4 và 4 là sẽ nói, OK, tốt, trở lại 4 lần thừa của 3. Và như bạn thấy, chúng tôi loại đến gần 1. Chúng tôi đang nhận được gần hơn và gần với trường hợp cơ sở. 

Và một khi chúng ta nhấn hợp cơ sở, tất cả các chức năng trước đó có câu trả lời mà họ đang tìm kiếm. Thừa của 2 đang nói trở lại 2 lần giai thừa của 1. Vâng, thừa của 1 trả về 1. Vì vậy, các cuộc gọi cho thừa 2 có thể trở lại 2 lần 1, và cho rằng trở lại thừa của 3, được chờ đợi kết quả đó. 

Và sau đó nó có thể tính toán kết quả của nó, 3 lần 2 là 6, và đưa nó trở lại thừa của 4. Và một lần nữa, chúng ta có một video trên các cuộc gọi stack nơi này được minh họa một chút nhiều hơn những gì tôi đang nói ngay bây giờ. Nhưng điều này là nó. Chỉ riêng điều này là giải pháp cho tính giai thừa của một số. 

Nó chỉ có bốn dòng mã. Đó là khá mát mẻ, phải không? Đó là loại sexy. 

Vì vậy, nói chung, nhưng không luôn luôn, một hàm đệ quy có thể thay thế một vòng lặp trong một hàm không đệ quy. Vì vậy, ở đây, bên cạnh, là lặp đi lặp lại phiên bản của các chức năng thừa. Cả hai tính toán chính xác những điều tương tự. 

Cả hai tính giai thừa của n. Các phiên bản bên trái sử dụng đệ quy để làm điều đó. Các phiên bản bên phải sử dụng lặp đi lặp lại để làm điều đó. 

Và thông báo, chúng ta phải khai báo một biến một sản phẩm số nguyên. Và sau đó chúng ta lặp. Vì vậy, miễn là n là lớn hơn 0, chúng tôi giữ nhân mà sản phẩm của n và giảm các n cho đến khi chúng tôi tính toán sản phẩm. Vì vậy, hai chức năng này, một lần nữa, làm chính xác những điều tương tự. Nhưng họ không làm điều đó trong chính xác theo cùng một cách. 

Bây giờ, nó có thể có nhiều hơn một cơ sở trường hợp hoặc nhiều hơn một trường hợp đệ quy, tùy thuộc về những gì chức năng của bạn đang cố gắng để làm. Bạn không nhất thiết chỉ giới hạn một trường hợp cơ sở duy nhất hoặc một đệ quy đơn trường hợp. Vì vậy, một ví dụ có với nhiều trường hợp cơ sở có thể là các this-- Dãy số Fibonacci. 

Bạn có thể nhớ lại từ còn học tiểu học rằng dãy Fibonacci được định nghĩa như this-- phần tử đầu tiên là 0. Yếu tố thứ hai là 1. Cả hai của những người chỉ là theo định nghĩa. 

Sau đó mọi phần tử khác được định nghĩa là tổng của n trừ đi 1 và n trừ đi 2. Vì vậy, yếu tố thứ ba sẽ là 0 + 1 là 1. Và sau đó yếu tố thứ tư sẽ là yếu tố thứ hai, 1, cộng với các yếu tố thứ ba, 1. Và đó sẽ là 2. Và như vậy và như vậy. 

Vì vậy, trong trường hợp này, chúng ta có hai trường hợp cơ sở. Nếu n là bằng 1, trở về 0. Nếu n là bằng 2, trở về 1. Nếu không, trở về Fibonacci của n trừ 1 cộng với Fibonacci của n trừ đi 2. 

Vì vậy, đó là nhiều trường hợp cơ sở. Còn nhiều trường hợp đệ quy? Vâng, có điều gì đó gọi là phỏng đoán Collatz. Tôi sẽ không nói, bạn biết đó là gì, bởi vì nó thực sự thức của chúng tôi vấn đề cho video đặc biệt này. Và đó là tập thể dục của chúng tôi để làm việc trên cùng. 

Vì vậy, đây là những gì Collatz phỏng đoán is-- nó áp dụng cho tất cả các số nguyên dương. Và nó đoán rằng nó luôn luôn có thể quay trở lại 1 nếu bạn làm theo các bước sau. Nếu n là 1, dừng lại. Chúng tôi đã trở lại với 1 nếu n là 1. 

Nếu không, đi qua này quá trình một lần nữa trên n chia cho 2. Và xem nếu bạn có thể lấy lại cho 1. Nếu không, nếu n là số lẻ, đi qua quá trình này một lần nữa trên 3n cộng với 1, hoặc 3 lần n + 1. Vì vậy, ở đây chúng tôi có một trường hợp cơ sở duy nhất. Nếu n là bằng 1, dừng lại. Chúng tôi sẽ không làm bất cứ đệ quy nhiều hơn. 

Nhưng chúng ta có hai trường hợp đệ quy. Nếu n là chẵn, chúng tôi làm một đệ quy trường hợp, gọi điện thoại n chia cho 2. Nếu n là số lẻ, chúng tôi làm một khác nhau trường hợp đệ quy trên 3 lần n + 1. 

Và vì vậy mục tiêu cho video này để mất một giây, tạm dừng các video, và thử viết này hàm đệ quy Collatz nơi bạn vượt qua trong một giá trị n, và nó tính toán có bao nhiêu bước nó cần để có được 1 nếu bạn bắt đầu từ n và bạn làm theo những bước lên trên. Nếu n là 1, phải mất 0 bước. Nếu không, nó sẽ một bước cộng tuy nhiên nhiều bước cần phải mất hai n chia cho 2 nếu n là chẵn, hoặc 3n cộng 1 nếu n là số lẻ. 

Bây giờ, tôi đã đặt lên trên màn hình ở đây một vài điều thử nghiệm cho bạn, một vài thử nghiệm các trường hợp cho bạn, để xem những gì các con số khác nhau là Collatz, và cũng là một minh họa các bước mà cần phải được đi qua, do đó bạn có thể loại nhìn thấy quá trình này trong hành động. Vì vậy, nếu n bằng 1, Collatz của n là 0. Bạn không cần phải làm bất cứ điều gì để có được trở lại 1. Bạn đã có. 

Nếu n là 2, phải mất một bước để có được 1. Bạn bắt đầu với 2. Vâng, 2 là không bằng 1. Vì vậy, nó sẽ là một bước Tuy nhiên cộng với nhiều bước nó mất trên n chia cho 2. 

2 chia cho 2 là 1. Vì vậy, phải mất một bước cộng tuy nhiên nhiều bước cần cho 1. 1 mất zero bước. 

Đối với 3, bạn có thể thấy, có khá một vài bước có liên quan. Bạn đi từ 3. Và sau đó bạn đi đến 10, 5, 16, 8, 4, 2, 1. Phải mất bảy bước để có được trở lại 1. Và như bạn thấy, có một vài trường hợp thử nghiệm khác ở đây để kiểm tra chương trình của bạn. Vì vậy, một lần nữa, tạm dừng video. Và tôi sẽ đi nhảy lại ngay bây giờ để những gì quá trình thực tế là ở đây, những phỏng đoán này là. 

Xem nếu bạn có thể tìm ra làm thế nào để xác định Collatz của n vì vậy mà nó tính toán có bao nhiêu các bước cần thiết để có được 1. Vì vậy, hy vọng, bạn đã tạm dừng video và bạn không phải chờ đợi tôi để cung cấp cho bạn câu trả lời ở đây. Nhưng nếu bạn đang có, cũng, đây là câu trả lời nào. 

Vì vậy, đây là một định nghĩa có thể của hàm Collatz. Cơ sở của chúng tôi case-- nếu n là bằng 1, chúng tôi trở về 0. Nó không mất bất kỳ bước để có được trở lại 1. 

Nếu không, chúng ta có hai cases-- đệ quy một cho số chẵn và một cho lẻ. Cách tôi kiểm tra số chẵn là để kiểm tra xem n mod 2 bằng 0. Điều này về cơ bản là, một lần nữa, đặt câu hỏi, nếu bạn nhớ lại những gì mod is-- nếu tôi chia n 2 là không có còn lại không? Đó sẽ là một số chẵn. 

Và vì vậy nếu n mod 2 bằng 0 là thử nghiệm là đây là một số chẵn. Nếu vậy, tôi muốn trở về 1, bởi vì điều này chắc chắn là thực hiện một bước cộng Collatz của bất cứ số là một nửa của tôi. Nếu không, tôi muốn quay trở lại 1 cộng Collatz của 3 lần n + 1. Đó là khác bước đệ quy mà chúng ta có thể áp dụng để tính toán Collatz-- số bước nó cần để có được trở lại đến 1 đưa ra một số. Vì vậy, hy vọng, ví dụ này đã cho bạn một chút của một hương vị của thủ tục đệ quy. Hy vọng rằng, bạn nghĩ rằng mã là một ít đẹp hơn nếu được thực hiện theo một cách đệ quy nhã. Nhưng thậm chí nếu không, đệ quy là một công cụ thực sự mạnh mẽ không kém. Và do đó, nó chắc chắn là điều để có được đầu của bạn xung quanh, bởi vì bạn sẽ có thể tạo ra chương trình khá mát mẻ sử dụng đệ quy mà nếu không có thể là phức tạp để viết nếu bạn đang sử dụng các vòng lặp và lặp đi lặp lại. Tôi Doug Lloyd. Đây là CS50.