Đệ quy - Short

Question 1

Khái niệm về hàm đệ quy

một hàm đệ quy được định nghĩa là một hàm tự gọi chính nó như là một phần trong quá trình thực thi của nó.

Question 2

Khái niệm về thủ tục đệ quy (mình nghĩ từ này không quan trọng)

Question 3

0:05
» DOUG LLOYD: Bạn có thể nghĩ rằng mã chỉ được sử dụng để hoàn thành một nhiệm vụ.

Question 4

> > Nhưng tin hay không tùy bạn, nếu bạn viết mã trong một thời gian dài,
0:17
bạn thực sự có thể coi mã là thứ gì đó đẹp đẽ.

Question 5

Nó giải quyết vấn đề theo một cách rất thú vị,
0:23
hoặc chỉ có một cái gì đó thực sự gọn gàng về hình thức (của mã code) của nó.
0:26 Bạn có thể đang cười nhạo tôi, nhưng đó là sự thật.

Question 6

Và đệ quy là một cách để có được ý tưởng
0:31
về mã đẹp, thanh lịch này.
Nó giải quyết các vấn đề theo những cách thú vị, dễ hình dung,
0:37
và ngắn đến bất ngờ.

Answer 6

Vậy đệ quy chỉ là 1 cách để làm cho mã đẹp và thanh lịch à.

Cái này lưu trữ những ưu điểm của đệ quy

Question 7

0:53 Nhưng một lần nữa, các thủ tục đệ quy này
0:55 sẽ rất thanh lịch bởi vì chúng sẽ
0:57 giải quyết vấn đề này mà không cần có tất cả các hàm khác
1:00 hoặc những vòng lặp dài này.

Answer 7

ưu điểm của đệ quy và (có thể) định nghĩa của từ thanh lịch đối với mã

Question 8

Chúng ta có thể mô tả việc triển khai một thuật toán là đặc biệt “sang trọng” nếu nó giải quyết vấn đề theo cách vừa thú vị vừa dễ hình dung.
Kỹ thuật đệ quy là một cách rất phổ biến để thực hiện một giải pháp “thanh lịch” như vậy.
Định nghĩa của một hàm đệ quy là một hàm gọi chính nó như là một phần của quá trình thực thi nó.

Question 9

Hàm giai thừa (n!) được xác định trên mọi số nguyên dương.
n! bằng tất cả các số nguyên dương nhỏ hơn hoặc bằng n, nhân với nhau.
Suy nghĩ về mặt lập trình, chúng ta sẽ xác định hàm toán học n! như fact(n).

Question 10

fact(1) = 1
fact(2) = 2 * 1
fact(3) = 3 * 2 * 1
fact(4) = 4 * 3 * 2 * 1
fact(5) = 5 * 4 * 3 * 2 * 1
…

fact(1) = 1
fact(2) = 2 * fact(1)
fact(3) = 3 * fact(2)
fact(4) = 4 * fact(3)
fact(5) = 5 * fact(4)
…

Question 11

fact(n) = n * fact(n - 1)

Question 12

Điều này tạo cơ sở cho một định nghĩa đệ quy của hàm giai thừa.
Mọi hàm đệ quy đều có hai trường hợp có thể áp dụng, với bất kỳ đầu vào nào.
Trường hợp cơ sở, khi được kích hoạt sẽ chấm dứt quá trình đệ quy.
Trường hợp đệ quy, đó là nơi đệ quy sẽ thực sự xảy ra.

Answer 12

Tìm định nghĩa

Question 13

int fact(int n)
{
// base case

// recursive case }

int fact(int n)
{
if (n == 1)
{
return 1;
}

// recursive case }

int fact(int n)
{
if (n == 1)
{
return 1;
}
else
{
return n * fact(n - 1);
}
}

int fact(int n)
{
if (n == 1)
return 1;
else
return n * fact(n - 1);
}

Question 14

call stack là đang chờ kết quả

Question 15

Trường hợp nhiều cơ số: Dãy số Fibonacci được xác định như sau:
Phần tử đầu tiên là 0.
Phần tử thứ hai là 1.
Phần tử thứ n là tổng của phần tử thứ (n-1) và thứ (n-2).

Nhiều trường hợp đệ quy: Phỏng đoán Collatz.

Answer 15

Nhiều trường hợp đệ quy

Question 16

Đệ quy: mã(code không phải mẫu mã) đẹp, thanh lịch, công cụ mạnh

Question 17

bởi vì bạn sẽ có thể tạo các chương trình khá thú vị bằng cách sử dụng đệ quy
13:41
điều đó có thể phức tạp để viết nếu bạn đang sử dụng các vòng lặp và phép lặp.

Answer 17

sử dụng các vòng lặp và phép lặp

Question 18

Giả thuyết Collatz được áp dụng cho các số nguyên dương và suy đoán rằng luôn có thể “quay lại 1” nếu bạn làm theo các bước sau:
Nếu n bằng 1 thì dừng.
Ngược lại, nếu n chẵn, lặp lại quá trình này với n/2.
Ngược lại, nếu n là số lẻ, lặp lại quá trình này trên 3n + 1.
Viết hàm đệ quy collatz(n) tính xem cần bao nhiêu bước để lên 1 nếu bạn bắt đầu từ n và lặp lại như đã nêu ở trên.

Question 19

int collatz(int n)
{
// base case
if (n == 1)
return 0;
// even numbers
else if ((n % 2) == 0)
return 1 + collatz(n / 2);
// odd numbers
else
return 1 + collatz(3 * n + 1);
}