Bỏ qua đến nội dung chính
Mục lục

Đệ quy trong Python (recursion): hàm tự gọi chính nó

AIDev Team · duyệt: Nguyễn Việt Chung

Bài 13/17 · Chương 8

Hàm

  • 8 phút
  • Cơ bản
  • Python 3.14
  • Cập nhật

Đệ 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ó:

python
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 1

Hà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:

python
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
0

Tổ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:

python
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(6), fibonacci(10))

KẾT QUẢ

8 55

Code 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:

python
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 21891

Tă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:

python
def giai_thua(n):
    if n <= 1:
        return 1
    return n * giai_thua(n - 1)

print(giai_thua(3))

KẾT QUẢ

6

Lờ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():

python
import sys
print(sys.getrecursionlimit())

KẾT QUẢ

1000

Chạ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

  1. Trong ví dụ giai thừa, nếu nhánh dừng viết return 0 thay cho return 1 thì giai_thua(4) trả về gì?

    • 24
    • 0
    • 4
  2. Hàm giai thừa có điều kiện dừng if n == 0: return 1. Gọi nó với n = -1 thì điều gì xảy ra?

    • Trả về 1, vì -1 nhỏ hơn 0
    • Trả về -1
    • Báo lỗi RecursionError, vì n đi -2, -3 và không bao giờ bằng 0
  3. 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 for trong 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
  4. Hàm tong_tien củ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
Đúng hết lần đầu +15 XP

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.

python
def dem_mon_dat(cac_gia, nguong):
    pass  # Viết thân hàm thay cho dòng này

Tó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 - 1 hay 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ủ đề

đệ quy python

Bài này có hữu ích?

Hỏi đáp

Đang tải câu hỏi…

Tham vấn chuyên môn

Nguyễn Việt Chung

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.
Biên soạn: AIDev Team · Rà soát · Quy trình biên tập