>> ZAMYLA: Để hiểu đệ quy, bạn phải
đầu tiên hiểu đệ quy.
Có đệ quy trong chương trình thiết kế phương tiện rằng bạn có tự tham chiếu
định nghĩa.
Cấu trúc dữ liệu đệ quy, ví dụ, là những cấu trúc dữ liệu
bao gồm bản thân trong định nghĩa.
Nhưng ngày hôm nay, chúng ta sẽ tập trung về chức năng đệ quy.
>> Nhớ lại rằng chức năng có đầu vào, đối số, và trả về một giá trị như họ
đầu ra đại diện sơ đồ này ở đây.
Chúng tôi sẽ nghĩ về hộp như cơ thể của chức năng, có chứa các bộ
hướng dẫn giải thích đầu vào và cung cấp một đầu ra.
Tham gia một cái nhìn gần hơn bên trong cơ thể của chức năng có thể tiết lộ các cuộc gọi đến
chức năng khác.
Có chức năng này đơn giản, foo, mà có một chuỗi duy nhất là đầu vào và
in bao nhiêu chữ cái chuỗi có.
Chức năng strlen, cho chiều dài chuỗi, được gọi là, có đầu ra là
cần thiết cho các cuộc gọi đến printf.
>> Bây giờ, những gì làm cho một hàm đệ quy đặc biệt là nó gọi chính nó.
Chúng ta có thể đại diện cho đệ quy gọi với mũi tên màu cam này
lặp lại cho chính nó.
Nhưng thực hiện nó một lần nữa chỉ sẽ thực hiện một cuộc gọi đệ quy, và
khác và khác.
Nhưng chức năng đệ quy không thể là vô hạn.
Họ phải kết thúc bằng cách nào đó, hoặc của bạn chương trình sẽ chạy mãi mãi.
>> Vì vậy chúng tôi cần phải tìm một cách để phá vỡ ra khỏi các cuộc gọi đệ quy.
Chúng tôi gọi đây là trường hợp cơ sở.
Khi điều kiện trường hợp cơ sở được đáp ứng, hàm trả về mà không làm
một cuộc gọi đệ quy.
Có chức năng này, hi, một hàm void mà phải mất một int n như đầu vào.
Trường hợp cơ sở đến trước.
Nếu n là nhỏ hơn không, in tạm biệt và trở lại Đối với tất cả các trường hợp khác, các
chức năng sẽ in hi và thực hiện cuộc gọi đệ quy.
Một cuộc gọi đến các chức năng hi với một giá trị đầu vào giảm đi.
>> Bây giờ, mặc dù chúng tôi in hi, các chức năng sẽ không chấm dứt cho đến khi chúng tôi
trở lại kiểu trả về của nó, trong trường hợp này có hiệu lực.
Vì vậy, đối với mỗi n khác hơn so với trường hợp cơ sở, chức năng này sẽ trở lại hi hi
n trừ đi 1.
Vì chức năng này không có hiệu lực, mặc dù chúng tôi sẽ không đánh một cách rõ ràng trở lại đây.
Chúng ta sẽ thực hiện các chức năng.
Vì vậy, gọi hi (3) sẽ in và hi thực hi (2) thực hiện các hi (1) một
thực hiện các hi (0), nơi điều kiện trường hợp cơ sở được đáp ứng.
Vì vậy, hi (0) in tạm biệt và trả về.
>> OK.
Vì vậy, bây giờ chúng ta hiểu những điều cơ bản của chức năng đệ quy, mà họ cần
ít nhất một trường hợp cơ sở cũng như một gọi đệ quy, chúng ta hãy chuyển sang một
Ví dụ có ý nghĩa hơn.
Một trong đó không chỉ trả lại làm mất hiệu lực không có vấn đề gì.
>> Chúng ta hãy nhìn vào các nhân tố hoạt động sử dụng phổ biến nhất trong
tính toán xác suất.
Thừa của n là sản phẩm của mỗi số nguyên dương nhỏ hơn
và bằng n.
Vì vậy, năm thừa là 5 lần 4 lần 3 lần 2 lần 1 để cung cấp cho 120.
Bốn thừa là 4 lần 3 lần 2 lần 1 để cung cấp cho 24.
Và cùng một quy tắc áp dụng với bất kỳ số nguyên dương.
>> Vậy làm thế nào chúng ta có thể viết đệ quy chức năng cho phép tính giai thừa
của một số?
Vâng, chúng tôi sẽ cần phải xác định cả hai trường hợp cơ sở và các cuộc gọi đệ quy.
Cuộc gọi đệ quy sẽ giống nhau cho tất cả các trường hợp ngoại trừ cho các cơ sở
trường hợp, có nghĩa là chúng tôi sẽ phải tìm thấy một mô hình mà sẽ cho chúng ta của chúng tôi
kết quả mong muốn.
>> Trong ví dụ này, xem như thế nào 5 thừa liên quan đến nhân 4 3 2 1
Và rất giống nhân được tìm thấy ở đây,
định nghĩa của 4 thừa.
Vì vậy, chúng ta thấy rằng 5 là thừa chỉ 5 lần 4 thừa.
Bây giờ không áp dụng mô hình này 4 factorial không?
Vâng.
Chúng ta thấy rằng 4 nhân tố có chứa các nhân 3 lần 2 lần 1,
rất giống như định nghĩa 3 thừa.
Vì vậy, 4 thừa bằng 4 lần 3 thừa, vv và vv của chúng tôi
mô hình gậy cho đến khi 1 nhân tố, trong đó theo định nghĩa là bằng 1.
>> Không có tích cực khác số nguyên trái.
Vì vậy, chúng ta có mô hình cho gọi đệ quy của chúng tôi.
n thừa bằng n lần giai thừa của n trừ đi 1.
Và trường hợp cơ sở của chúng tôi?
Điều đó sẽ chỉ được định nghĩa của chúng tôi 1 thừa.
>> Vì vậy, bây giờ chúng tôi có thể chuyển sang viết mã cho chức năng.
Đối với trường hợp cơ sở, chúng tôi sẽ có điều kiện n bằng bình đẳng 1, nơi
chúng tôi sẽ trả lại 1.
Sau đó chuyển sang cuộc gọi đệ quy, chúng tôi sẽ trở lại n lần
thừa của n trừ đi 1.
>> Bây giờ hãy kiểm tra của chúng tôi này.
Chúng ta hãy cố gắng thừa 4.
Mỗi chức năng của chúng tôi nó bằng đến 4 lần thừa (3).
Thừa (3) bằng 3 lần thừa (2).
Thừa (2) tương đương với 2 lần thừa (1), trả về 1.
Thừa (2) bây giờ trả về 2 lần 1, 2.
Thừa (3) bây giờ có thể quay trở lại 3 lần 2, 6.
Và cuối cùng, thừa (4) trả 4 lần 6, 24.
>> Nếu bạn đang gặp phải bất kỳ khó khăn với các cuộc gọi đệ quy, giả vờ rằng
chức năng công trình đã.
Những gì tôi có ý nghĩa của việc này là bạn nên tin tưởng các cuộc gọi đệ quy của bạn trở lại
các giá trị đúng.
Ví dụ, nếu tôi biết rằng thừa (5) bằng 5 lần
thừa (4), tôi sẽ tin tưởng rằng thừa (4) sẽ cho tôi 24.
Nghĩ về nó như là một biến, nếu bạn sẽ, như thể bạn đã được xác định
thừa (4).
Vì vậy, đối với bất kỳ thừa (n), nó sản phẩm của n và
giai thừa trước đó.
Và thừa trước đây thu được bằng cách gọi
thừa của n trừ đi 1.
>> Bây giờ, xem bạn có thể thực hiện một đệ quy hoạt động cho mình.
Tải lên thiết bị đầu cuối của bạn, hoặc run.cs50.net, và viết một số tiền chức năng
mà phải mất một số nguyên n và trả về tổng của tất cả liên tiếp tích cực
số nguyên từ n đến 1.
Tôi đã viết ra số tiền của một số giá trị để giúp bạn của chúng tôi.
Đầu tiên, tìm ra các trường hợp cơ sở điều kiện.
Sau đó, nhìn vào tổng hợp (5).
Bạn có thể thể hiện nó trong điều kiện của tổng khác?
Bây giờ, những gì về tổng hợp (4)?
Làm thế nào bạn có thể thể hiện tổng hợp (4) về số tiền khác?
>> Một khi bạn đã tổng hợp (5) và tổng hợp (4) thể hiện trong điều khoản của các khoản tiền khác, xem
nếu bạn có thể xác định một mô hình để tổng hợp (n).
Nếu không, hãy thử một vài số điện thoại khác và thể hiện số tiền của họ trong
về số lượng khác.
Bằng cách xác định mô hình rời rạc số, bạn cũng trên đường đến
xác định mô hình cho bất kỳ n.
>> Đệ quy là một công cụ thực sự mạnh mẽ, nên dĩ nhiên nó không giới hạn
chức năng toán học.
Đệ quy có thể được sử dụng rất hiệu quả khi giao dịch với cây chẳng hạn.
Kiểm tra ngắn trên cây cho một xem xét kỹ lưỡng hơn, nhưng bây giờ
nhớ lại rằng cây tìm kiếm nhị phân, trong Đặc biệt, được tạo thành từ các nút, mỗi
với một giá trị và hai con trỏ nút.
Thông thường, điều này được thể hiện bằng nút cha có một dòng trỏ
đến nút con trái và một đến nút con phải.
Cấu trúc của một tìm kiếm nhị phân cây vay cũng chính nó
để tìm kiếm đệ quy.
Cuộc gọi đệ quy hoặc đi qua các trái hoặc nút phải, nhưng hơn
đó trong ngắn cây.
>> Nói rằng bạn muốn thực hiện một thao tác trên mỗi nút duy nhất trong một cây nhị phân.
Làm thế nào bạn có thể đi về điều đó?
Vâng, bạn có thể viết một đệ quy chức năng thực hiện các hoạt động
trên nút cha và làm cho một đệ quy gọi để cùng chức năng,
đi qua trong bên trái và các nút con phải.
Ví dụ, chức năng này, foo, mà thay đổi giá trị của một nút cho trước và
tất cả các con của nó là 1.
Trường hợp cơ sở của một nguyên nhân nút vô giá trị chức năng quay trở lại, cho thấy
mà không có bất kỳ nút còn lại trong đó cây con.
>> Chúng ta hãy đi qua nó.
Phụ huynh đầu tiên là 13.
Chúng tôi thay đổi giá trị 1, và sau đó gọi chức năng của chúng tôi bên trái cũng
như bên phải.
Chức năng, foo, được gọi là bên trái cây con đầu tiên, do đó nút bên trái
sẽ được bố trí 1 và foo sẽ được gọi là con cái của nút đó,
đầu tiên bên trái và sau đó bên phải, vv và vv.
Và nói với họ rằng các chi nhánh không có trẻ em nữa vì vậy quá trình tương tự
sẽ tiếp tục cho các em ngay cho đến khi nút toàn bộ cây của là
bố trí 1.
>> Như bạn thấy, bạn không giới hạn chỉ cần một cuộc gọi đệ quy.
Cũng giống như nhiều như sẽ có được công việc thực hiện.
Nếu bạn đã có một cây trong đó mỗi nút có ba người con,
Trái, giữa và phải không?
Làm thế nào bạn sẽ chỉnh sửa foo?
Vâng, đơn giản.
Chỉ cần thêm một cuộc gọi đệ quy và vượt qua trong con trỏ nút giữa.
>> Đệ quy là rất mạnh mẽ và không để đề cập đến thanh lịch, nhưng nó có thể là một
khái niệm khó khăn lúc đầu, vì vậy hãy bệnh nhân và mất thời gian của bạn.
Bắt đầu với trường hợp cơ sở.
Nó thường là đơn giản nhất để xác định, và sau đó bạn có thể làm việc
ngược từ đó.
Bạn biết bạn cần phải đạt được của bạn trường hợp cơ sở, vì vậy sức mạnh mà
cung cấp cho bạn một vài gợi ý.
Cố gắng thể hiện một trường hợp cụ thể trong về các trường hợp khác, hoặc tại các bộ.
>> Cảm ơn cho xem cái này ngắn.
Ít nhất, bây giờ bạn có thể hiểu câu nói đùa như thế này.
Tên tôi là Zamyla, và đây là CS50.
>> Có chức năng này, hi, một khoảng trống chức năng mà mất
một int, n, như đầu vào.
Trường hợp cơ sở đến trước.
Nếu n là nhỏ hơn 0, in "Bye" và trở lại.