Đệ quy trong Python (recursion): hàm tự gọi chính nó
Bài 13/17 · Chương 8
Hàm
- 8 phút
- Cơ bản
- Python 3.14
- Cập nhật
Trong bài này · 12
Đệ quy trong Python (recursion) là cách viết một hàm tự gọi chính nó, mỗi lần trên một phần nhỏ hơn của bài toán, cho tới khi phần đó nhỏ đến mức trả lời được ngay. Bạn dùng đệ quy khi bài toán lớn được tả bằng chính nó ở cỡ nhỏ hơn, như tổng một hóa đơn bằng giá món đầu cộng tổng các món còn lại.
Cần biết trước: lệnh return, câu lệnh if else và list.
Hàm tự gọi chính nó
Lớp có bốn học viên cần xếp thứ tự thuyết trình. Người đầu có bốn lựa chọn, người sau còn ba, rồi hai, rồi một: số cách là 4 * 3 * 2 * 1, gọi là giai thừa của 4. Giai thừa của 4 lại chính là 4 nhân giai thừa của 3, nên hàm tính giai thừa gọi lại chính nó:
def giai_thua(n):
if n <= 1:
return 1
return n * giai_thua(n - 1)
print(giai_thua(4))
print(giai_thua(1), giai_thua(0))KẾT QUẢ
24
1 1Hàm đệ quy có hai phần. Nhánh if n <= 1 là điều kiện dừng: nó trả lời ngay mà không gọi lại hàm. Dòng return n * giai_thua(n - 1) là bước đệ quy: nó giao phần việc nhỏ hơn cho một lời gọi mới rồi dùng kết quả của lời gọi đó. Giống người đứng cuối hàng muốn biết mình đứng thứ mấy: hỏi người phía trước, người đó lại hỏi người trước nữa, cho tới người đầu hàng trả lời "thứ nhất" mà không phải hỏi ai.
Đổi giai_thua(4) thành giai_thua(5) rồi chạy lại: dòng đầu in 120.
Điều kiện dừng và phần nhỏ hơn của bài toán
Muốn đệ quy dừng, mỗi lời gọi phải tiến gần tới điều kiện dừng. Với list, phần nhỏ hơn thường là list bỏ đi phần tử đầu, lấy bằng lát cắt [1:], và điều kiện dừng là list rỗng:
def tong_tien(cac_gia):
if len(cac_gia) == 0:
return 0
return cac_gia[0] + tong_tien(cac_gia[1:])
print(tong_tien([29000, 32000, 35000]))
print(tong_tien([]))KẾT QUẢ
96000
0Tổng của [29000, 32000, 35000] là 29000 cộng tổng của [32000, 35000], và cứ thế tới list rỗng, có tổng là 0. Mỗi lời gọi nhận một list ngắn hơn một phần tử, nên sau đúng ba lần cắt là chạm điều kiện dừng. Lời gọi với list rỗng đi thẳng vào nhánh dừng, nên hàm đúng cả với hóa đơn chưa có món nào.
Fibonacci: một lời gọi sinh hai lời gọi
Dãy Fibonacci bắt đầu bằng 0, 1, và mỗi số sau bằng tổng hai số đứng ngay trước nó. Định nghĩa đó viết thẳng thành hàm có hai lời gọi đệ quy:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(6), fibonacci(10))KẾT QUẢ
8 55Code ngắn và đọc giống hệt định nghĩa, nhưng mỗi lời gọi sinh thêm hai lời gọi, và các lời gọi đó tính lại cùng một số nhiều lần. Hàm dưới đây đếm số lần fibonacci(n) được gọi, cũng bằng đệ quy:
def so_lan_goi(n):
if n <= 1:
return 1
return 1 + so_lan_goi(n - 1) + so_lan_goi(n - 2)
print(so_lan_goi(10), so_lan_goi(20))KẾT QUẢ
177 21891Tăng n thêm 10 làm số lời gọi tăng hơn trăm lần: so_lan_goi(30) đã là 2692537. Python có sẵn functools.lru_cache() để hàm nhớ kết quả đã tính, mỗi fibonacci(k) khi đó chỉ tính một lần. Bài functools dạy cách dùng nó.
Mỗi lời gọi chờ lời gọi bên trong
Bấm Chạy từng bước để xem giai_thua(3) mở ba lời gọi lồng nhau trước khi có phép nhân nào được làm:
def giai_thua(n):
if n <= 1:
return 1
return n * giai_thua(n - 1)
print(giai_thua(3))KẾT QUẢ
6Lời gọi với n = 3 dừng ở dòng return để chờ giai_thua(2), lời gọi đó lại chờ giai_thua(1). Chỉ khi giai_thua(1) trả về 1 thì các phép nhân mới chạy ngược ra: 2 * 1, rồi 3 * 2. Mỗi lời gọi đang chờ chiếm một tầng, và Python giới hạn số tầng. Bản Python trên máy tính đặt giới hạn mặc định là 1000, đọc được bằng sys.getrecursionlimit():
import sys
print(sys.getrecursionlimit())KẾT QUẢ
1000Chạy trên máy của bạn · Đoạn này cần Python cài trên máy, trang không chạy được.
Dòng import sys nạp module sys có sẵn của Python, bài import dạy kỹ. Số này là của Python cài trên máy; trình chạy trên trang có thể khác, nên khối trên chỉ để đọc.
Kiểm tra nhanh
Trong ví dụ giai thừa, nếu nhánh dừng viết
return 0thay choreturn 1thìgiai_thua(4)trả về gì?- 24
- 0
- 4
Hàm giai thừa có điều kiện dừng
if n == 0: return 1. Gọi nó vớin = -1thì điều gì xảy ra?- Trả về
1, vì-1nhỏ hơn0 - Trả về
-1 - Báo lỗi RecursionError, vì
nđi-2,-3và không bao giờ bằng0
- Trả về
Một hàm đệ quy cần những gì để dừng được?
- Một nhánh trả về kết quả mà không gọi lại hàm
- Một vòng lặp
fortrong thân hàm - Mỗi lời gọi đệ quy nhận đối số gần điều kiện dừng hơn
- Dòng
returnở cuối thân hàm
Hàm
tong_tiencủa bài có điều kiện dừng đúng. Gọi nó với một list 2000 giá thì sao?- Báo lỗi RecursionError, vì cần 2000 tầng gọi lồng nhau
- Trả về tổng của 2000 giá
- Báo lỗi IndexError ở phần tử cuối
Bài tập
Đếm món từ ngưỡng giá bằng đệ quy
Viết thân hàm dem_mon_dat(cac_gia, nguong), đếm số món trong list cac_gia có giá từ nguong trở lên. Không dùng vòng lặp for, while, lambda, các hàm sum(), filter(), map(), reduce() hay phương thức count(): hàm phải tự gọi chính nó trên phần còn lại của list. Hàm không sửa list cac_gia.
Ví dụ: dem_mon_dat([29000, 45000, 35000, 32000], 35000) trả về 2.
Trả về: số món có giá từ ngưỡng trở lên, một int.
def dem_mon_dat(cac_gia, nguong):
pass # Viết thân hàm thay cho dòng nàyTóm tắt
Hàm đệ quy tự gọi chính nó trên một phần nhỏ hơn của bài toán, rồi dùng kết quả của lời gọi đó.
Điều kiện dừng là nhánh trả lời ngay, không gọi lại hàm; nó phải trả về đúng đáp án của bài toán nhỏ nhất.
Mỗi lời gọi phải đưa đối số tiến gần điều kiện dừng, như
n - 1hay lát cắt[1:].Thiếu điều kiện dừng, hoặc không bao giờ chạm tới nó, thì Python báo
RecursionError.Mỗi lời gọi đang chờ chiếm một tầng; giới hạn mặc định 1000 tầng, nên dãy dài hợp với vòng lặp hơn.
Fibonacci đệ quy hai nhánh tính lại cùng một số nhiều lần:
fibonacci(20)cần 21891 lời gọi.
Câu hỏi thường gặp
Hàm đệ quy trong Python có chậm hơn vòng lặp không?
Thường là có, vì mỗi lời gọi hàm tốn thêm công hơn một lượt của vòng lặp for, và Python không tự gộp các lời gọi đệ quy lại. Với bài toán mà đệ quy tính lại cùng một giá trị nhiều lần, như Fibonacci, khoảng cách còn lớn hơn nhiều. Chọn đệ quy khi nó làm code dễ đọc hơn và số tầng nhỏ.
Khi nào nên dùng đệ quy (recursion) thay cho vòng lặp?
Khi dữ liệu có hình lồng nhau, như list lồng nhau mà số lớp không biết trước, thư mục chứa thư mục con, hay sơ đồ phân cấp. Vòng lặp khó đi hết những hình này, còn đệ quy chỉ cần một nhánh cho phần tử đơn và một lời gọi cho phần lồng bên trong. Dãy phẳng và dài thì dùng vòng lặp.
Có tăng được giới hạn đệ quy của Python không?
Có, bằng sys.setrecursionlimit(), nhưng đó thường là dấu hiệu nên viết lại bằng vòng lặp while hay for. Đặt giới hạn quá cao có thể làm Python bị sập (crash), thay cho một RecursionError đọc được.
Viết Fibonacci đệ quy thế nào để chạy nhanh?
Cho hàm nhớ kết quả của từng fibonacci(k) đã tính, để mỗi số chỉ tính một lần. Python có sẵn công cụ làm việc này trong module functools, đã nhắc ở mục Fibonacci. Một cách khác là tính bằng vòng lặp từ hai số đầu, giữ hai số gần nhất ở mỗi lượt.
Chủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE
- Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
- Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
- Xây hệ thống AI cho doanh nghiệp tại VietPlatform.