Gần đây tôi tình cờ gặp một câu hỏi trên Quora khi có người hỏi liệu anh ta có thể giải bài toán Tháp Hà Nội bằng phép lặp thay vì đệ quy không. Tôi nhận thấy các khái niệm đôi khi có thể được sử dụng thay thế cho nhau và chúng rất giống nhau
Khái niệm Đệ quy và Lặp lại là thực hiện lặp đi lặp lại một tập lệnh. Sự khác biệt giữa chúng là đệ quy chỉ đơn giản là một cuộc gọi phương thức trong đó phương thức được gọi giống với phương thức thực hiện cuộc gọi trong khi phép lặp là khi một vòng lặp được thực hiện lặp đi lặp lại cho đến khi một điều kiện nhất định được đáp ứng. Về cơ bản, cả đệ quy và lặp đều phụ thuộc vào một điều kiện để biết khi nào nên dừng nhưng đệ quy chỉ đơn giản là một quá trình, luôn được áp dụng cho một hàm
Một ví dụ về đệ quy được hiển thị bên dưới
và đây là một ví dụ về phép lặp
Sự khác biệt chính giữa đệ quy và lặp lại
- Câu lệnh điều kiện quyết định việc kết thúc đệ quy trong khi giá trị của biến điều khiển quyết định việc kết thúc câu lệnh lặp [ngoại trừ trường hợp vòng lặp while]
- Đệ quy vô hạn có thể dẫn đến sự cố hệ thống trong khi đó, phép lặp vô hạn tiêu tốn chu kỳ CPU
- Đệ quy liên tục gọi cơ chế và do đó, chi phí chung của các lệnh gọi phương thức. Điều này có thể tốn kém cả về thời gian xử lý và không gian bộ nhớ trong khi việc lặp lại không
- Đệ quy làm cho mã nhỏ hơn trong khi phép lặp làm cho nó dài hơn
Đây là một số khác biệt chính giữa phép lặp và đệ quy. Tôi hy vọng điều này đã được giải thích
Cả đệ quy và lặp đều không phải là một kỹ thuật ưu việt nói chung. Trên thực tế, bất kỳ mã đệ quy nào cũng có thể được viết dưới dạng mã lặp với vòng lặp và ngăn xếp. Đệ quy không có một số sức mạnh đặc biệt cho phép nó thực hiện các phép tính mà thuật toán lặp không thể. Và bất kỳ vòng lặp nào cũng có thể được viết lại dưới dạng hàm đệ quy
Chương này so sánh và đối chiếu đệ quy và lặp. Chúng ta sẽ xem xét các hàm giai thừa và Fibonacci cổ điển và xem tại sao các thuật toán đệ quy của chúng lại có những điểm yếu nghiêm trọng. Chúng ta cũng sẽ khám phá những hiểu biết sâu sắc mà một cách tiếp cận đệ quy có thể mang lại bằng cách xem xét một thuật toán lũy thừa. Nhìn chung, chương này làm sáng tỏ vẻ đẹp được cho là của các thuật toán đệ quy và chỉ ra khi nào một giải pháp đệ quy hữu ích và khi nào thì không.
Tính giai thừa
Nhiều khóa học khoa học máy tính sử dụng phép tính giai thừa như một ví dụ cổ điển về hàm đệ quy. Giai thừa của một số nguyên [tạm gọi là n] là tích của tất cả các số nguyên từ 1 đến n. Ví dụ: giai thừa của 4 là 4 × 3 × 2 × 1 hoặc 24. Dấu chấm than là ký hiệu toán học cho giai thừa, như trong 4. , nghĩa là giai thừa của 4. hiển thị một số giai thừa đầu tiên
Bảng 2-1. Giai thừa của vài số nguyên đầu tiên
n. Biểu mẫu mở rộngProduct1. =1=12. =1×2=23. =1×2×3=64. =1 × 2 × 3 × 4=245. =1 × 2 × 3 × 4 × 5=1206. =1 × 2 × 3 × 4 × 5 × 6=7207. =1 × 2 × 3 × 4 × 5 × 6 × 7=5,0408. =1 × 2 × 3 × 4 × 5 × 6 × 7 × 8=40,320Giai thừa được sử dụng trong tất cả các loại tính toán—ví dụ: tìm số lượng hoán vị cho một thứ gì đó. Nếu bạn muốn biết có bao nhiêu cách sắp xếp thứ tự bốn người — Alice, Bob, Carol và David — thành một hàng, câu trả lời là giai thừa của 4. Bốn người có thể xếp hàng đầu tiên [4]; . Số cách sắp xếp mọi người theo hàng—nghĩa là số hoán vị—là giai thừa của số người
Bây giờ, hãy xem xét cả cách tiếp cận lặp và đệ quy để tính giai thừa
Thuật toán thừa số lặp
Tính giai thừa lặp đi lặp lại khá đơn giản. nhân các số nguyên 1 đến và bao gồm n trong một vòng lặp. Các thuật toán lặp luôn sử dụng một vòng lặp. Giai thừaByIteration. chương trình py trông như thế này
con trăn
def factorial[number]:
product = 1
for i in range[1, number + 1]:
product = product * i
return product
print[factorial[5]]Và một giai thừaByIteration. chương trình html trông như thế này
JavaScript
Khi bạn chạy mã này, đầu ra sẽ hiển thị phép tính cho 5. như thế này
120Không có gì sai với giải pháp lặp để tính giai thừa; . Nhưng chúng ta cũng hãy xem thuật toán đệ quy để hiểu sâu hơn về bản chất của giai thừa và bản thân đệ quy
Thuật toán thừa số đệ quy
Lưu ý rằng giai thừa của 4 là 4 × 3 × 2 × 1 và giai thừa của 5 là 5 × 4 × 3 × 2 × 1. Vì vậy, bạn có thể nói rằng 5. = 5 × 4. Đây là đệ quy vì định nghĩa giai thừa của 5 [hoặc bất kỳ số n nào] bao gồm định nghĩa của giai thừa của 4 [số n – 1]. Lần lượt, 4. = 4 × 3. , v.v., cho đến khi bạn phải tính 1. , trường hợp cơ sở, đơn giản là 1
giai thừaByRecursion. py Chương trình Python sử dụng thuật toán giai thừa đệ quy
con trăn
def factorial[number]:
if number == 1:
# BASE CASE
return 1
else:
# RECURSIVE CASE
❶ return number * factorial[number - 1]
print[factorial[5]]Và giai thừaByRecursion. html chương trình JavaScript với mã tương đương trông như thế này
JavaScript
Khi bạn chạy mã này để tính toán 5. đệ quy, đầu ra khớp với đầu ra của chương trình lặp
120Đối với nhiều lập trình viên, mã đệ quy này có vẻ lạ. Bạn biết rằng
120Sự nhầm lẫn phát sinh do trường hợp đệ quy có một dòng ❶, một nửa trong số đó được thực hiện trước lệnh gọi đệ quy và một nửa trong số đó diễn ra sau khi lệnh gọi đệ quy trả về. Chúng tôi không quen với ý tưởng chỉ thực thi một nửa dòng mã tại một thời điểm
Nửa đầu là
def factorial[number]:
if number == 1:
# BASE CASE
return 1
else:
# RECURSIVE CASE
❶ return number * factorial[number - 1]
print[factorial[5]]def factorial[number]:
if number == 1:
# BASE CASE
return 1
else:
# RECURSIVE CASE
❶ return number * factorial[number - 1]
print[factorial[5]]Lần tiếp theo mã chạy với đối tượng khung cũ là sau khi
def factorial[number]:
if number == 1:
# BASE CASE
return 1
else:
# RECURSIVE CASE
❶ return number * factorial[number - 1]
print[factorial[5]]120def factorial[number]:
if number == 1:
# BASE CASE
return 1
else:
# RECURSIVE CASE
❶ return number * factorial[number - 1]
print[factorial[5]]def factorial[number]:
if number == 1:
# BASE CASE
return 1
else:
# RECURSIVE CASE
❶ return number * factorial[number - 1]
print[factorial[5]]def factorial[number]:
if number == 1:
# BASE CASE
return 1
else:
# RECURSIVE CASE
❶ return number * factorial[number - 1]
print[factorial[5]]def factorial[number]:
if number == 1:
# BASE CASE
return 1
else:
# RECURSIVE CASE
❶ return number * factorial[number - 1]
print[factorial[5]]def factorial[number]:
if number == 1:
# BASE CASE
return 1
else:
# RECURSIVE CASE
❶ return number * factorial[number - 1]
print[factorial[5]]def factorial[number]:
if number == 1:
# BASE CASE
return 1
else:
# RECURSIVE CASE
❶ return number * factorial[number - 1]
print[factorial[5]]120theo dõi trạng thái của ngăn xếp cuộc gọi khi các đối tượng khung được đẩy [xảy ra khi các lệnh gọi hàm đệ quy được thực hiện] và các đối tượng khung được bật [khi các lệnh gọi hàm đệ quy trả về]. Lưu ý rằng phép nhân xảy ra sau khi gọi đệ quy, không phải trước
Khi hàm ban đầu gọi tới ____1_______2 trả về, nó sẽ trả về giai thừa đã tính
Tại sao thuật toán thừa số đệ quy lại khủng khiếp
Việc triển khai đệ quy để tính giai thừa có một điểm yếu nghiêm trọng. Tính giai thừa của 5 yêu cầu năm lần gọi hàm đệ quy. Điều này có nghĩa là năm đối tượng khung được đặt trên ngăn xếp cuộc gọi trước khi đạt đến trường hợp cơ sở. Điều này không quy mô
Nếu bạn muốn tính giai thừa của 1.001, hàm đệ quy
Hình 2-1. Trạng thái của ngăn xếp cuộc gọi khi các cuộc gọi đệ quy tới
Mặt khác, thuật toán lặp giai thừa sẽ hoàn thành phép tính một cách nhanh chóng và hiệu quả. Có thể tránh tràn ngăn xếp bằng cách sử dụng một kỹ thuật có sẵn trong một số ngôn ngữ lập trình được gọi là tối ưu hóa cuộc gọi đuôi. Chương 8 đề cập đến chủ đề này. Tuy nhiên, kỹ thuật này làm phức tạp thêm việc thực hiện hàm đệ quy. Để tính giai thừa, phương pháp lặp là đơn giản nhất và trực tiếp nhất
Tính dãy Fibonacci
Dãy Fibonacci là một ví dụ cổ điển khác để giới thiệu đệ quy. Về mặt toán học, dãy số nguyên Fibonacci bắt đầu bằng các số 1 và 1 [hoặc đôi khi là 0 và 1]. Số tiếp theo trong dãy bằng tổng hai số liền trước. Điều này tạo ra chuỗi 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, v.v., mãi mãi
Nếu chúng ta gọi hai số mới nhất trong dãy số a và b, bạn có thể thấy trình tự phát triển như thế nào
Hình 2-2. Mỗi số của dãy Fibonacci là tổng của hai số liền trước
Hãy khám phá một số ví dụ về mã của cả giải pháp lặp và đệ quy để tạo số Fibonacci
Thuật toán Fibonacci lặp
Ví dụ về Fibonacci lặp rất đơn giản, bao gồm một vòng lặp
con trăn
def fibonacci[nthNumber]:
❶ a, b = 1, 1
print['a = %s, b = %s' % [a, b]]
for i in range[1, nthNumber]:
❷ a, b = b, a + b # Get the next Fibonacci number.
print['a = %s, b = %s' % [a, b]]
return a
print[fibonacci[10]]FibonacciByIteration này. chương trình html có mã JavaScript tương đương
JavaScript
Khi bạn chạy mã này để tính số Fibonacci thứ 10, kết quả sẽ như thế này
a = 1, b = 1
a = 1, b = 2
a = 2, b = 3
--snip--
a = 34, b = 55
55Chương trình chỉ cần theo dõi hai số mới nhất của dãy tại một thời điểm. Vì hai số đầu tiên trong dãy Fibonacci được định nghĩa là 1, nên chúng ta lưu trữ
Thuật toán Fibonacci đệ quy
Tính toán các số Fibonacci liên quan đến thuộc tính đệ quy. Ví dụ, nếu bạn muốn tính số Fibonacci thứ 10, bạn cộng các số Fibonacci thứ chín và thứ tám với nhau. Để tính các số Fibonacci đó, bạn cộng các số Fibonacci thứ tám và thứ bảy, sau đó là các số Fibonacci thứ bảy và thứ sáu. Rất nhiều tính toán lặp lại xảy ra. lưu ý rằng việc thêm các số Fibonacci thứ chín và thứ tám liên quan đến việc tính toán lại số Fibonacci thứ tám. Bạn tiếp tục đệ quy này cho đến khi đạt được trường hợp cơ bản của số Fibonacci thứ nhất hoặc thứ hai, luôn luôn là 1
Hàm Fibonacci đệ quy nằm trong fibonacciByRecursion này. chương trình py Python
def fibonacci[nthNumber]:
print['fibonacci[%s] called.' % [nthNumber]]
if nthNumber == 1 or nthNumber == 2: ❶
# BASE CASE
print['Call to fibonacci[%s] returning 1.' % [nthNumber]]
return 1
else:
# RECURSIVE CASE
print['Calling fibonacci[%s] and fibonacci[%s].' % [nthNumber - 1, nthNumber - 2]]
result = fibonacci[nthNumber - 1] + fibonacci[nthNumber - 2]
print['Call to fibonacci[%s] returning %s.' % [nthNumber, result]]
return result
print[fibonacci[10]]FibonacciByRecursion này. tệp html có chương trình JavaScript tương đương
Khi bạn chạy mã này để tính số Fibonacci thứ 10, kết quả sẽ như thế này
Phần lớn mã là để hiển thị đầu ra này, nhưng bản thân hàm
120120def fibonacci[nthNumber]:
❶ a, b = 1, 1
print['a = %s, b = %s' % [a, b]]
for i in range[1, nthNumber]:
❷ a, b = b, a + b # Get the next Fibonacci number.
print['a = %s, b = %s' % [a, b]]
return a
print[fibonacci[10]]def fibonacci[nthNumber]:
❶ a, b = 1, 1
print['a = %s, b = %s' % [a, b]]
for i in range[1, nthNumber]:
❷ a, b = b, a + b # Get the next Fibonacci number.
print['a = %s, b = %s' % [a, b]]
return a
print[fibonacci[10]]def fibonacci[nthNumber]:
❶ a, b = 1, 1
print['a = %s, b = %s' % [a, b]]
for i in range[1, nthNumber]:
❷ a, b = b, a + b # Get the next Fibonacci number.
print['a = %s, b = %s' % [a, b]]
return a
print[fibonacci[10]]120def fibonacci[nthNumber]:
❶ a, b = 1, 1
print['a = %s, b = %s' % [a, b]]
for i in range[1, nthNumber]:
❷ a, b = b, a + b # Get the next Fibonacci number.
print['a = %s, b = %s' % [a, b]]
return a
print[fibonacci[10]]Hãy nhớ ví dụ giai thừa đệ quy có phần “trước lệnh gọi đệ quy” và “sau lệnh gọi đệ quy” như thế nào? . “trước lệnh gọi đệ quy đầu tiên,” “sau lệnh gọi đệ quy đầu tiên nhưng trước lệnh gọi đệ quy thứ hai,” và “sau lệnh gọi đệ quy thứ hai. ” Nhưng các nguyên tắc tương tự được áp dụng. Và đừng nghĩ rằng vì đã đạt đến trường hợp cơ sở, nên không còn mã nào để chạy sau một trong hai lệnh gọi đệ quy. Thuật toán đệ quy chỉ kết thúc sau khi lời gọi hàm ban đầu được trả về
Bạn có thể hỏi, “Không phải giải pháp Fibonacci lặp lại đơn giản hơn giải pháp Fibonacci đệ quy sao?” . ” Tệ hơn nữa, giải pháp đệ quy có một sự kém hiệu quả nghiêm trọng sẽ được giải thích trong phần tiếp theo
Tại sao thuật toán Fibonacci đệ quy lại khủng khiếp
Giống như thuật toán giai thừa đệ quy, thuật toán Fibonacci đệ quy cũng mắc một điểm yếu nghiêm trọng. nó lặp đi lặp lại các phép tính giống nhau. cho thấy cách gọi
def fibonacci[nthNumber]:
❶ a, b = 1, 1
print['a = %s, b = %s' % [a, b]]
for i in range[1, nthNumber]:
❷ a, b = b, a + b # Get the next Fibonacci number.
print['a = %s, b = %s' % [a, b]]
return a
print[fibonacci[10]]def fibonacci[nthNumber]:
❶ a, b = 1, 1
print['a = %s, b = %s' % [a, b]]
for i in range[1, nthNumber]:
❷ a, b = b, a + b # Get the next Fibonacci number.
print['a = %s, b = %s' % [a, b]]
return a
print[fibonacci[10]]def fibonacci[nthNumber]:
❶ a, b = 1, 1
print['a = %s, b = %s' % [a, b]]
for i in range[1, nthNumber]:
❷ a, b = b, a + b # Get the next Fibonacci number.
print['a = %s, b = %s' % [a, b]]
return a
print[fibonacci[10]]Hình 2-3. Sơ đồ cây của các lệnh gọi hàm đệ quy được thực hiện bắt đầu bằng
def fibonacci[nthNumber]:
❶ a, b = 1, 1
print['a = %s, b = %s' % [a, b]]
for i in range[1, nthNumber]:
❷ a, b = b, a + b # Get the next Fibonacci number.
print['a = %s, b = %s' % [a, b]]
return a
print[fibonacci[10]]Điều này gây ra một loạt các lệnh gọi hàm khác cho đến khi chúng đạt đến các trường hợp cơ sở là
Chuyển đổi thuật toán đệ quy thành thuật toán lặp
Luôn có thể chuyển đổi thuật toán đệ quy thành thuật toán lặp. Trong khi các hàm đệ quy lặp lại một phép tính bằng cách gọi chính chúng, thì việc lặp lại này có thể được thực hiện thay vì một vòng lặp. Các hàm đệ quy cũng sử dụng ngăn xếp cuộc gọi; . Do đó, bất kỳ thuật toán đệ quy nào cũng có thể được thực hiện lặp đi lặp lại bằng cách sử dụng vòng lặp và ngăn xếp.
Để chứng minh điều này, đây là giai thừaEmulateRecursion. py, một chương trình Python thực hiện thuật toán lặp để mô phỏng thuật toán đệ quy
Giai thừaEmulateRecursion. chương trình html chứa JavaScript tương đương
Lưu ý rằng chương trình này không có chức năng đệ quy; . Chương trình mô phỏng các lệnh gọi hàm đệ quy bằng cách sử dụng danh sách dưới dạng cấu trúc dữ liệu ngăn xếp [được lưu trữ trong biến
120Bất kỳ hàm đệ quy nào cũng có thể được viết lặp lại theo cách này. Mặc dù mã này cực kỳ khó hiểu và bạn sẽ không bao giờ viết thuật toán giai thừa trong thế giới thực theo cách này, nhưng nó chứng tỏ rằng đệ quy không có khả năng bẩm sinh mà mã lặp không có.
Chuyển đổi thuật toán lặp thành thuật toán đệ quy
Tương tự như vậy, luôn luôn có thể chuyển đổi thuật toán lặp thành thuật toán đệ quy. Thuật toán lặp đơn giản là mã sử dụng vòng lặp. Mã được thực thi lặp lại [phần thân của vòng lặp] có thể được đặt trong phần thân của hàm đệ quy. Và giống như mã trong phần thân của vòng lặp được thực thi lặp đi lặp lại, chúng ta cần liên tục gọi hàm để thực thi mã của nó. Chúng ta có thể làm điều này bằng cách gọi hàm từ chính hàm đó, tạo một hàm đệ quy
Mã Python trong lời chào. py thể hiện việc in
a = 1, b = 1
a = 1, b = 2
a = 2, b = 3
--snip--
a = 34, b = 55
55con trăn
Mã JavaScript tương đương có trong hello. html
JavaScript
Đầu ra của các chương trình này trông như thế này
Vòng lặp
a = 1, b = 1
a = 1, b = 2
a = 2, b = 3
--snip--
a = 34, b = 55
55a = 1, b = 1
a = 1, b = 2
a = 2, b = 3
--snip--
a = 34, b = 55
55a = 1, b = 1
a = 1, b = 2
a = 2, b = 3
--snip--
a = 34, b = 55
55Đối với một ví dụ thực tế hơn, sau đây là các hàm lặp và đệ quy trả về chỉ mục của một chuỗi con,
a = 1, b = 1
a = 1, b = 2
a = 2, b = 3
--snip--
a = 34, b = 55
55a = 1, b = 1
a = 1, b = 2
a = 2, b = 3
--snip--
a = 34, b = 55
55a = 1, b = 1
a = 1, b = 2
a = 2, b = 3
--snip--
a = 34, b = 55
55a = 1, b = 1
a = 1, b = 2
a = 2, b = 3
--snip--
a = 34, b = 55
55con trăn
Chuỗi tìm kiếm này. chương trình html có phiên bản JavaScript tương đương
JavaScript
Các chương trình này thực hiện cuộc gọi tới
a = 1, b = 1
a = 1, b = 2
a = 2, b = 3
--snip--
a = 34, b = 55
55a = 1, b = 1
a = 1, b = 2
a = 2, b = 3
--snip--
a = 34, b = 55
55def fibonacci[nthNumber]:
print['fibonacci[%s] called.' % [nthNumber]]
if nthNumber == 1 or nthNumber == 2: ❶
# BASE CASE
print['Call to fibonacci[%s] returning 1.' % [nthNumber]]
return 1
else:
# RECURSIVE CASE
print['Calling fibonacci[%s] and fibonacci[%s].' % [nthNumber - 1, nthNumber - 2]]
result = fibonacci[nthNumber - 1] + fibonacci[nthNumber - 2]
print['Call to fibonacci[%s] returning %s.' % [nthNumber, result]]
return result
print[fibonacci[10]]def fibonacci[nthNumber]:
print['fibonacci[%s] called.' % [nthNumber]]
if nthNumber == 1 or nthNumber == 2: ❶
# BASE CASE
print['Call to fibonacci[%s] returning 1.' % [nthNumber]]
return 1
else:
# RECURSIVE CASE
print['Calling fibonacci[%s] and fibonacci[%s].' % [nthNumber - 1, nthNumber - 2]]
result = fibonacci[nthNumber - 1] + fibonacci[nthNumber - 2]
print['Call to fibonacci[%s] returning %s.' % [nthNumber, result]]
return result
print[fibonacci[10]]def fibonacci[nthNumber]:
print['fibonacci[%s] called.' % [nthNumber]]
if nthNumber == 1 or nthNumber == 2: ❶
# BASE CASE
print['Call to fibonacci[%s] returning 1.' % [nthNumber]]
return 1
else:
# RECURSIVE CASE
print['Calling fibonacci[%s] and fibonacci[%s].' % [nthNumber - 1, nthNumber - 2]]
result = fibonacci[nthNumber - 1] + fibonacci[nthNumber - 2]
print['Call to fibonacci[%s] returning %s.' % [nthNumber, result]]
return result
print[fibonacci[10]]Các chương trình trong phần này chứng minh rằng luôn có thể biến bất kỳ vòng lặp nào thành một hàm đệ quy tương đương. Mặc dù có thể thay thế một vòng lặp bằng đệ quy, nhưng tôi khuyên bạn không nên làm điều đó. Đây là thực hiện đệ quy vì lợi ích của đệ quy và vì đệ quy thường khó hiểu hơn mã lặp, nên khả năng đọc mã sẽ kém đi
nghiên cứu điển hình. Tính số mũ
Mặc dù đệ quy không nhất thiết tạo ra mã tốt hơn, nhưng sử dụng phương pháp đệ quy có thể cung cấp cho bạn những hiểu biết mới về vấn đề lập trình của bạn. Như một trường hợp nghiên cứu, hãy kiểm tra cách tính số mũ
Số mũ được tính bằng cách nhân một số với chính nó. Ví dụ: số mũ “ba lũy thừa sáu” hay 36, bằng phép nhân 3 với chính nó sáu lần. 3 × 3 × 3 × 3 × 3 × 3 = 729. Đây là một phép toán phổ biến đến nỗi Python có toán tử
def fibonacci[nthNumber]:
print['fibonacci[%s] called.' % [nthNumber]]
if nthNumber == 1 or nthNumber == 2: ❶
# BASE CASE
print['Call to fibonacci[%s] returning 1.' % [nthNumber]]
return 1
else:
# RECURSIVE CASE
print['Calling fibonacci[%s] and fibonacci[%s].' % [nthNumber - 1, nthNumber - 2]]
result = fibonacci[nthNumber - 1] + fibonacci[nthNumber - 2]
print['Call to fibonacci[%s] returning %s.' % [nthNumber, result]]
return result
print[fibonacci[10]]def fibonacci[nthNumber]:
print['fibonacci[%s] called.' % [nthNumber]]
if nthNumber == 1 or nthNumber == 2: ❶
# BASE CASE
print['Call to fibonacci[%s] returning 1.' % [nthNumber]]
return 1
else:
# RECURSIVE CASE
print['Calling fibonacci[%s] and fibonacci[%s].' % [nthNumber - 1, nthNumber - 2]]
result = fibonacci[nthNumber - 1] + fibonacci[nthNumber - 2]
print['Call to fibonacci[%s] returning %s.' % [nthNumber, result]]
return result
print[fibonacci[10]]def fibonacci[nthNumber]:
print['fibonacci[%s] called.' % [nthNumber]]
if nthNumber == 1 or nthNumber == 2: ❶
# BASE CASE
print['Call to fibonacci[%s] returning 1.' % [nthNumber]]
return 1
else:
# RECURSIVE CASE
print['Calling fibonacci[%s] and fibonacci[%s].' % [nthNumber - 1, nthNumber - 2]]
result = fibonacci[nthNumber - 1] + fibonacci[nthNumber - 2]
print['Call to fibonacci[%s] returning %s.' % [nthNumber, result]]
return result
print[fibonacci[10]]def fibonacci[nthNumber]:
print['fibonacci[%s] called.' % [nthNumber]]
if nthNumber == 1 or nthNumber == 2: ❶
# BASE CASE
print['Call to fibonacci[%s] returning 1.' % [nthNumber]]
return 1
else:
# RECURSIVE CASE
print['Calling fibonacci[%s] and fibonacci[%s].' % [nthNumber - 1, nthNumber - 2]]
result = fibonacci[nthNumber - 1] + fibonacci[nthNumber - 2]
print['Call to fibonacci[%s] returning %s.' % [nthNumber, result]]
return result
print[fibonacci[10]]Nhưng hãy viết mã tính toán số mũ của riêng chúng ta. Giải pháp rất đơn giản. tạo một vòng lặp liên tục nhân một số và trả về kết quả cuối cùng. Đây là một số mũ lặp đi lặp lạiByIteration. chương trình py Python
con trăn
120Và đây là một số mũ JavaScript tương đươngByIteration. html program
JavaScript
When you run these programs, the output looks like this
120This is a straightforward calculation that we can easily write with a loop. The downside to using a loop is that the function slows as the exponents get larger. calculating 312 takes twice as long as 36, and 3600 takes one hundred times as long as 36. In the next section, we address this by thinking recursively
Creating a Recursive Exponents Function
Hãy nghĩ xem một giải pháp đệ quy cho phép lũy thừa của 36 sẽ là gì. Because of the associative property of multiplication, 3 × 3 × 3 × 3 × 3 × 3 is the same as [3 × 3 × 3] × [3 × 3 × 3], which is the same as [3 × 3 × 3]2. And since [3 × 3 × 3] is the same as 33, we can determine that 36 is the same as [33]2. This is an example of what mathematics calls the power rule. [am]n = amn. Mathematics also gives us the product rule. an × am = an + m, including an × a = an + 1
We can use these mathematical rules to make an
def fibonacci[nthNumber]:
print['fibonacci[%s] called.' % [nthNumber]]
if nthNumber == 1 or nthNumber == 2: ❶
# BASE CASE
print['Call to fibonacci[%s] returning 1.' % [nthNumber]]
return 1
else:
# RECURSIVE CASE
print['Calling fibonacci[%s] and fibonacci[%s].' % [nthNumber - 1, nthNumber - 2]]
result = fibonacci[nthNumber - 1] + fibonacci[nthNumber - 2]
print['Call to fibonacci[%s] returning %s.' % [nthNumber, result]]
return result
print[fibonacci[10]]def fibonacci[nthNumber]:
print['fibonacci[%s] called.' % [nthNumber]]
if nthNumber == 1 or nthNumber == 2: ❶
# BASE CASE
print['Call to fibonacci[%s] returning 1.' % [nthNumber]]
return 1
else:
# RECURSIVE CASE
print['Calling fibonacci[%s] and fibonacci[%s].' % [nthNumber - 1, nthNumber - 2]]
result = fibonacci[nthNumber - 1] + fibonacci[nthNumber - 2]
print['Call to fibonacci[%s] returning %s.' % [nthNumber, result]]
return result
print[fibonacci[10]]def fibonacci[nthNumber]:
print['fibonacci[%s] called.' % [nthNumber]]
if nthNumber == 1 or nthNumber == 2: ❶
# BASE CASE
print['Call to fibonacci[%s] returning 1.' % [nthNumber]]
return 1
else:
# RECURSIVE CASE
print['Calling fibonacci[%s] and fibonacci[%s].' % [nthNumber - 1, nthNumber - 2]]
result = fibonacci[nthNumber - 1] + fibonacci[nthNumber - 2]
print['Call to fibonacci[%s] returning %s.' % [nthNumber, result]]
return result
print[fibonacci[10]]That works for even-numbered exponents, but what about for odd-numbered exponents? If we had to calculate 37, or 3 × 3 × 3 × 3 × 3 × 3 × 3, this is the same as [3 × 3 × 3 × 3 × 3 × 3] × 3, or [36] × 3. Then we can make the same recursive call to calculate 36
Those are the recursive cases, but what are the base cases? Mathematically speaking, any number to the zeroth power is defined as 1, while any number to the first power is the number itself. So for any function call
def fibonacci[nthNumber]:
❶ a, b = 1, 1
print['a = %s, b = %s' % [a, b]]
for i in range[1, nthNumber]:
❷ a, b = b, a + b # Get the next Fibonacci number.
print['a = %s, b = %s' % [a, b]]
return a
print[fibonacci[10]]def fibonacci[nthNumber]:
❶ a, b = 1, 1
print['a = %s, b = %s' % [a, b]]
for i in range[1, nthNumber]:
❷ a, b = b, a + b # Get the next Fibonacci number.
print['a = %s, b = %s' % [a, b]]
return a
print[fibonacci[10]]Using all this information, we can write code for the
def fibonacci[nthNumber]:
print['fibonacci[%s] called.' % [nthNumber]]
if nthNumber == 1 or nthNumber == 2: ❶
# BASE CASE
print['Call to fibonacci[%s] returning 1.' % [nthNumber]]
return 1
else:
# RECURSIVE CASE
print['Calling fibonacci[%s] and fibonacci[%s].' % [nthNumber - 1, nthNumber - 2]]
result = fibonacci[nthNumber - 1] + fibonacci[nthNumber - 2]
print['Call to fibonacci[%s] returning %s.' % [nthNumber, result]]
return result
print[fibonacci[10]]con trăn
120And here is the equivalent JavaScript code in exponentByRecursion. html
JavaScript
When you run this code, the output is identical to the iterative version
120Each recursive call effectively cuts the problem size in half. This is what makes our recursive exponent algorithm faster than the iterative version; calculating 31000 iteratively entails 1,000 multiplication operations, while doing it recursively requires only 23 multiplications and divisions. When running the Python code under a performance profiler, calculating 31000 iteratively 100,000 times takes 10. 633 seconds, but the recursive calculation takes only 0. 406 seconds. That is a huge improvement
Creating an Iterative Exponents Function Based on Recursive Insights
Our original iterative exponents function took a straightforward approach. loop the same number of times as the exponent power. However, this doesn’t scale well for larger powers. Our recursive implementation forced us to think about how to break this problem into smaller subproblems. This approach turns out to be much more efficient
Because every recursive algorithm has an equivalent iterative algorithm, we could make a new iterative exponents function based on the power rule that the recursive algorithm uses. The following exponentWithPowerRule. py program has such a function
con trăn
120Here is the equivalent JavaScript program in exponentWithPowerRule. html
JavaScript
Our algorithm keeps reducing
For example, calling
def fibonacci[nthNumber]:
❶ a, b = 1, 1
print['a = %s, b = %s' % [a, b]]
for i in range[1, nthNumber]:
❷ a, b = b, a + b # Get the next Fibonacci number.
print['a = %s, b = %s' % [a, b]]
return a
print[fibonacci[10]]def fibonacci[nthNumber]:
❶ a, b = 1, 1
print['a = %s, b = %s' % [a, b]]
for i in range[1, nthNumber]:
❷ a, b = b, a + b # Get the next Fibonacci number.
print['a = %s, b = %s' % [a, b]]
return a
print[fibonacci[10]]def fibonacci[nthNumber]:
❶ a, b = 1, 1
print['a = %s, b = %s' % [a, b]]
for i in range[1, nthNumber]:
❷ a, b = b, a + b # Get the next Fibonacci number.
print['a = %s, b = %s' % [a, b]]
return a
print[fibonacci[10]]def fibonacci[nthNumber]:
❶ a, b = 1, 1
print['a = %s, b = %s' % [a, b]]
for i in range[1, nthNumber]:
❷ a, b = b, a + b # Get the next Fibonacci number.
print['a = %s, b = %s' % [a, b]]
return a
print[fibonacci[10]]To perform the second step, we start the
def fibonacci[nthNumber]:
❶ a, b = 1, 1
print['a = %s, b = %s' % [a, b]]
for i in range[1, nthNumber]:
❷ a, b = b, a + b # Get the next Fibonacci number.
print['a = %s, b = %s' % [a, b]]
return a
print[fibonacci[10]]The stack in
Figure 2-4. The stack in
When you run this code, the output is identical to the other exponent programs
120The iterative exponents function that uses the power rule has the improved performance of the recursive algorithm, while not suffering from the risk of a stack overflow. We might not have thought of this new, improved iterative algorithm without the insights of recursive thinking
When Do You Need to Use Recursion?
You never need to use recursion. No programming problem requires recursion. This chapter has shown that recursion has no magical power to do things that iterative code in a loop with a stack data structure cannot do. In fact, a recursive function might be an overcomplicated solution for what you’re trying to achieve
However, as the exponent functions we created in the previous section show, recursion can provide new insights into how to think about our programming problem. Three features of a programming problem, when present, make it especially suitable to a recursive approach
- It involves a tree-like structure
- It involves backtracking
- It isn’t so deeply recursive as to potentially cause a stack overflow
A tree has a self-similar structure. the branching points look similar to the root of a smaller subtree. Recursion often deals with self-similarity and problems that can be divided into smaller, similar subproblems. The root of the tree is analogous to the first call to a recursive function, the branching points are analogous to recursive cases, and the leaves are analogous to the base cases where no more recursive calls are made
A maze is also a good example of a problem that has a tree-like structure and requires backtracking. In a maze, the branching points occur wherever you must pick one of many paths to follow. If you reach a dead end, you’ve encountered the base case. You must then backtrack to a previous branching point to select a different path to follow
shows a maze’s path visually morphed to look like a biological tree. Despite the visual difference between the maze paths and the tree-shaped paths, their branching points are related to each other in the same way. Mathematically, these graphs are equivalent
Figure 2-5. A maze [left] along with its interior paths [center] morphed to match a biological tree’s shape [right]
Many programming problems have this tree-like structure at their core. For example, a filesystem has a tree-like structure; the subfolders look like the root folders of a smaller filesystem. compares a filesystem to a tree
Figure 2-6. A filesystem is similar to a tree structure
Tìm kiếm một tên tệp cụ thể trong một thư mục là một vấn đề đệ quy. you search the folder and then recursively search the folder’s subfolders. Folders with no subfolders are the base cases that cause the recursive searching to stop. If your recursive algorithm doesn’t find the filename it’s looking for, it backtracks to a previous parent folder and continues searching from there
The third point is a matter of practicality. If your tree structure has so many levels of branches that a recursive function would cause a stack overflow before it can reach the leaves, then recursion isn’t a suitable solution
Mặt khác, đệ quy là cách tiếp cận tốt nhất để tạo trình biên dịch ngôn ngữ lập trình. Compiler design is its own expansive subject and beyond the scope of this book. But programming languages have a set of grammar rules that can break source code into a tree structure similar to the way grammar rules can break English sentences into a tree diagram. Recursion is an ideal technique to apply to compilers
We’ll identify many recursive algorithms in this book, and they often have the tree-like structure or backtracking features that lend themselves to recursion well
Coming Up with Recursive Algorithms
Hopefully, this chapter has given you a firm idea of how recursive functions compare to the iterative algorithms you’re likely more familiar with. The rest of this book dives into the details of various recursive algorithms. Nhưng bạn nên viết các hàm đệ quy của riêng mình như thế nào?
The first step is always to identify the recursive case and the base case. You can take a top-down approach by breaking the problem into subproblems that are similar to the original problem but smaller; this is your recursive case. Then consider when the subproblems are small enough to have a trivial answer; this is your base case. Your recursive function may have more than one recursive case or base case, but all recursive functions will always have at least one recursive case and at least one base case
The recursive Fibonacci algorithm is an example. A Fibonacci number is the sum of the previous two Fibonacci numbers. We can break the problem of finding a Fibonacci number into the subproblems of finding two smaller Fibonacci numbers. We know the first two Fibonacci numbers are both 1, so that provides the base case answer once the subproblems are small enough
Sometimes it helps to take a bottom-up approach and consider the base case first, and then see how larger and larger problems are constructed and solved from there. The recursive factorial problem is an example. The factorial of 1. is 1. This forms the base case. The next factorial is 2. , and you create it by multiplying 1. by 2. The factorial after that, 3. , is created by multiplying 2. by 3, and so on. From this general pattern, we can figure out what the recursive case for our algorithm will be
Summary
In this chapter, we covered calculating factorials and the Fibonacci sequence, two classic recursive programming problems. This chapter featured both iterative and recursive implementations for these algorithms. Despite being classic examples of recursion, their recursive algorithms suffer from critical flaws. The recursive factorial function can cause stack overflows, while the recursive Fibonacci function performs so many redundant calculations that it’s far too slow to be effective in the real world
We explored how to create recursive algorithms from iterative algorithms and how to create iterative algorithms from recursive algorithms. Iterative algorithms use a loop, and any recursive algorithm can be performed iteratively by using a loop and a stack data structure. Recursion is often an overly complicated solution, but programming problems that involve a tree-like structure and backtracking are particularly suitable for recursive implementations
Writing recursive functions is a skill that improves with practice and experience. The rest of this book covers several well-known recursion examples and explores their strengths and limitations
Further Reading
You can find more information about comparing iteration and recursion in the Computerphile YouTube channel’s video “Programming Loops vs. Recursion” at https. //youtu. be/HXNhEYqFo0o. If you want to compare the performance of iterative and recursive functions, you need to learn how to use a profiler. Python profilers are explained in Chapter 13 of my book Beyond the Basic Stuff with Python [No Starch Press, 2020], which can be read at https. //inventwithpython. com/beyond/chapter13. html. The official Python documentation also covers profilers at https. //docs. python. org/3/library/profile. html. The Firefox profiler for JavaScript is explained on Mozilla’s website at https. //developer. mozilla. org/en-US/docs/Tools/Performance. Other browsers have profilers similar to Firefox’s