Đệ quy trong C
Đệ quy (recursion) là kỹ thuật trong đó một hàm tự gọi chính nó. Nghe có vẻ lạ, nhưng nó phản ánh đúng nhiều bài toán có cấu trúc tự lặp lại: lời giải của bài lớn được xây từ lời giải của bài nhỏ hơn cùng dạng.
Hãy bắt đầu bằng một việc bạn làm mỗi ngày mà không để ý. Bạn mở thư mục Tai lieu, thấy
vài tệp và vài thư mục con. Muốn đếm tổng số tệp bên trong, bạn đếm các tệp thấy ngay,
rồi mở từng thư mục con và làm đúng công việc vừa rồi với nó. Thư mục con lại có thư
mục con nữa thì bạn lại lặp lại. Bạn không cần biết cây thư mục sâu bao nhiêu tầng, bạn
chỉ cần biết một quy tắc và biết lúc nào dừng, đó là khi thư mục không còn thư mục con.
Cách nghĩ ấy chính là đệ quy: mô tả bài toán bằng chính nó, ở quy mô nhỏ hơn.
Vòng lặp cũng lặp đi lặp lại, nhưng nó lặp theo chiều ngang, đi hết phần tử này tới
phần tử khác trên cùng một mức. Đệ quy lặp theo chiều sâu, mỗi lần nó tạm gác bài toán
đang làm để đi giải một bài nhỏ hơn, giải xong mới quay về làm nốt. Nhờ vậy đệ quy rất
hợp với những cấu trúc tự lồng nhau, nơi ta không biết trước độ sâu: cây thư mục, biểu
thức toán học có ngoặc lồng ngoặc, hay các định nghĩa toán học kiểu n! = n * (n-1)!.
Cái giá của sự gọn gàng đó là bộ nhớ và tốc độ, và phần lớn bài học hôm nay dành để hiểu cái giá ấy: máy tính giữ lại những gì trong lúc hàm chờ chính nó, vì sao chờ quá sâu thì chương trình sập, và vì sao có những hàm đệ quy đúng về logic nhưng chậm tới mức không dùng được.
Thử ngay: xem đệ quy chạy từng bước
Bấm ▶ Chạy (hoặc kéo thanh trượt) để theo dõi ngăn xếp lời gọi của giaiThua(3): các
khung chồng lên nhau khi hàm đi xuống mỗi lúc một sâu, rồi giá trị trả ngược lên trong khi
từng khung được gỡ. Chỗ hàm ngừng gọi chính nó và quay đầu gọi là trường hợp cơ sở, và
các mục bên dưới sẽ giải thích vì sao thiếu nó là chương trình sập.
1#include <stdio.h>23long giaiThua(int n) {4 if (n == 0)5 return 1;6 return n * giaiThua(n - 1);7}89int main(void) {10 long kq = giaiThua(3);11 printf("3! = %ld\n", kq);12 return 0;13}
Ý tưởng và trường hợp cơ sở
Một hàm đệ quy luôn có hai phần.
- Trường hợp cơ sở (base case): trường hợp đơn giản nhất, trả về kết quả ngay mà không cần gọi đệ quy. Đây là điểm dừng.
- Bước đệ quy (recursive step): hàm gọi lại chính nó với dữ liệu nhỏ hơn, tiến dần về trường hợp cơ sở.
Thiếu trường hợp cơ sở, hoặc bước đệ quy không tiến về phía cơ sở, hàm sẽ tự gọi mãi không dừng. Đây là lỗi nghiêm trọng, dẫn tới tràn ngăn xếp ở phần sau.
Khi ngồi viết một hàm đệ quy, hãy tự trả lời ba câu hỏi theo đúng thứ tự này. Thứ nhất, bài toán nhỏ nhất mà tôi trả lời được ngay không cần suy nghĩ là bài nào? Đó là trường hợp cơ sở, và hãy viết nó ra trước tiên. Thứ hai, giả sử đã có sẵn lời giải của bài nhỏ hơn một bậc, tôi ghép nó vào thế nào để ra lời giải của bài hiện tại? Đó là bước truy hồi. Thứ ba, mỗi lần gọi lại, dữ liệu của tôi có thật sự nhỏ đi không, và nó có chắc chắn chạm tới trường hợp cơ sở sau hữu hạn bước không?
Câu hỏi thứ hai là chỗ người mới hay bị tắc, vì họ cố hình dung toàn bộ chuỗi lời gọi trong đầu cùng một lúc. Đừng làm vậy, đầu người không đủ chỗ. Hãy tin rằng lời gọi con sẽ trả về đúng kết quả, cứ dùng kết quả đó như dùng một hàm đã viết sẵn. Niềm tin ấy không phải mê tín: nó đúng vì bài toán con nhỏ hơn, và cứ nhỏ dần thì cuối cùng sẽ rơi vào trường hợp cơ sở, nơi ta biết chắc câu trả lời. Người ta gọi lối lập luận này là quy nạp, và nó là nền móng của mọi hàm đệ quy đúng.
Nhiều bạn viết bước đệ quy mà quên kiểm tra câu hỏi thứ ba. Ví dụ hàm tính giai thừa ở
dưới sẽ chạy mãi nếu ta gọi giaiThua(-1): giá trị n giảm còn -2, -3 và cứ giảm
mãi, không bao giờ bằng 0 nên không bao giờ chạm cơ sở. Sửa bằng cách đổi điều kiện cơ
sở thành if (n <= 0) return 1;, hoặc chặn đầu vào âm ngay từ đầu. Bài học: dữ liệu
phải tiến về phía cơ sở trên mọi đầu vào hợp lệ, chứ không chỉ trên đầu vào bạn nghĩ
tới lúc viết.
Ví dụ giai thừa
Giai thừa của n, ký hiệu n!, là tích các số nguyên từ 1 tới n. Định nghĩa đệ quy
rất tự nhiên: 0! = 1 và n! = n * (n-1)! với n > 0. Vế đầu là trường hợp cơ sở, vế
sau là bước đệ quy.
#include <stdio.h>
// n! defined recursively: 0! = 1, n! = n * (n-1)!
long giaiThua(int n) {
if (n == 0) // base case: stop here
return 1;
return n * giaiThua(n - 1); // recursive step, smaller n
}
int main(void) {
printf("3! = %ld\n", giaiThua(3)); // 6
return 0;
}
Hãy lần theo lời gọi giaiThua(3). Vì 3 khác 0, hàm trả về 3 * giaiThua(2). Để tính
được, nó phải chờ giaiThua(2), mà cái này lại chờ giaiThua(1), rồi giaiThua(1) chờ
giaiThua(0). Tới đây gặp trường hợp cơ sở, giaiThua(0) trả về 1, và kết quả lan ngược
lên: 1 * 1 = 1, rồi 2 * 1 = 2, rồi 3 * 2 = 6.
Đệ quy và ngăn xếp
Mỗi lời gọi hàm chưa hoàn tất được hệ thống lưu trong một vùng nhớ gọi là ngăn xếp
(call stack). Mỗi lần gọi tạo một khung (stack frame) chứa tham số và biến cục bộ
của lần gọi đó. Với giaiThua(3), có lúc bốn khung cùng nằm trên ngăn xếp:
giaiThua(3), giaiThua(2), giaiThua(1), giaiThua(0). Khi gặp trường hợp cơ sở, các
khung lần lượt được giải phóng theo thứ tự ngược lại.
Vì ngăn xếp có dung lượng hữu hạn, nếu đệ quy quá sâu (ví dụ thiếu trường hợp cơ sở nên gọi vô hạn), ngăn xếp sẽ đầy và chương trình bị lỗi tràn ngăn xếp (stack overflow), thường biểu hiện bằng việc chương trình dừng đột ngột.
Hãy nhìn kỹ hơn vào một khung. Nó không chỉ chứa tham số n. Nó còn chứa các biến cục
bộ của lần gọi đó, và quan trọng nhất là địa chỉ trở về, tức chỗ trong mã lệnh mà
máy phải quay lại sau khi hàm kết thúc. Chính nhờ địa chỉ trở về mà giaiThua(2) biết
phải trả kết quả cho giaiThua(3) chứ không phải cho ai khác, dù cả bốn khung đều là
cùng một hàm. Mỗi lần gọi có một bản sao riêng của n, hoàn toàn độc lập: n bằng 3 ở
khung này và bằng 2 ở khung kia, chúng không đụng nhau. Đây là điều người mới hay hiểu
sai, họ tưởng chỉ có một biến n duy nhất bị thay đổi liên tục.
Điểm mấu chốt tiếp theo: khung của giaiThua(3) không được giải phóng khi nó gọi
giaiThua(2). Nó vẫn nằm đó, đóng băng giữa chừng, vì nó còn dở việc. Nó đã tính được
vế 3 nhưng chưa có vế giaiThua(2) để nhân vào, nên phải chờ. Chỉ khi lời gọi con trả
về, nó mới nhân xong và ra đi. Nghĩa là số khung tồn tại cùng lúc bằng đúng độ sâu đệ
quy, và bộ nhớ ngăn xếp mà chương trình chiếm tỉ lệ thuận với độ sâu ấy.
Ngăn xếp thường chỉ được cấp vài megabyte, ít hơn nhiều so với vùng nhớ động. Với mỗi khung chiếm vài chục byte, ta gọi được cỡ vài chục nghìn tới vài trăm nghìn tầng trước khi hết chỗ. Nghe thì nhiều, nhưng nếu bạn viết hàm đệ quy duyệt một danh sách một triệu phần tử theo kiểu mỗi phần tử một tầng, chương trình sẽ sập. Đó là lý do đệ quy hợp với những bài mà độ sâu tăng chậm, chẳng hạn tăng theo logarit của dữ liệu như tìm kiếm nhị phân, hơn là những bài mà độ sâu tăng tuyến tính theo số phần tử.
Tràn ngăn xếp không in ra dòng lỗi tử tế. Chương trình chỉ đơn giản chết giữa chừng, trên
Windows là hộp thoại báo dừng hoạt động, trên Linux là dòng chữ Segmentation fault.
Nhiều bạn thấy vậy liền đi tìm lỗi ở phép tính hay ở mảng, trong khi nguyên nhân nằm ở
hàm đệ quy không chịu dừng. Dấu hiệu nhận biết: chương trình chạy được với dữ liệu nhỏ
nhưng chết ngay với dữ liệu lớn hơn, hoặc chết tức thì với mọi dữ liệu nếu bạn quên hẳn
trường hợp cơ sở.
Mỗi hàm đệ quy phải bảo đảm hai điều: có trường hợp cơ sở rõ ràng, và mỗi bước đệ quy phải tiến gần hơn về trường hợp cơ sở. Quên một trong hai dẫn tới đệ quy vô hạn.
Ví dụ Fibonacci
Dãy Fibonacci định nghĩa: F(0) = 0, F(1) = 1, và F(n) = F(n-1) + F(n-2) với
n >= 2. Ở đây có hai trường hợp cơ sở (n == 0 và n == 1) và bước đệ quy gọi hàm
hai lần.
#include <stdio.h>
// F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)
int fibo(int n) {
if (n == 0) return 0; // base case 1
if (n == 1) return 1; // base case 2
return fibo(n - 1) + fibo(n - 2); // two recursive calls
}
int main(void) {
for (int i = 0; i < 10; i++)
printf("%d ", fibo(i)); // 0 1 1 2 3 5 8 13 21 34
printf("\n");
return 0;
}
Bản đệ quy của Fibonacci rất dễ đọc nhưng kém hiệu quả: fibo(n) tính lại nhiều giá trị
trùng nhau, số lời gọi tăng theo hàm mũ. Với n lớn chương trình sẽ rất chậm. Cách dùng
vòng lặp tính tuần tự từ nhỏ lên lớn nhanh hơn nhiều.
Vì sao Fibonacci đệ quy lại chậm
Câu cảnh báo trên rất dễ đọc lướt rồi quên. Hãy dừng lại và xem chính xác điều gì xảy ra, vì đây là bài học quan trọng nhất về chi phí của đệ quy.
Hãy vẽ ra cây lời gọi của fibo(5). Nó gọi fibo(4) và fibo(3). Đến lượt fibo(4)
gọi fibo(3) và fibo(2). Bạn thấy vấn đề chưa? fibo(3) bị tính hai lần: một lần
do fibo(5) gọi thẳng, một lần do fibo(4) gọi. Mà mỗi lần tính fibo(3) lại kéo theo
cả một cây con bên dưới nó, gồm fibo(2), fibo(1), fibo(0). Đi sâu thêm nữa thì
fibo(2) bị tính ba lần, fibo(1) bị tính năm lần. Máy không hề nhớ rằng nó vừa tính
xong fibo(3) cách đây một phần nghìn giây; mỗi lời gọi là một khung mới, tính lại từ
đầu, không ai lưu kết quả cũ.
Số lời gọi vì thế phình rất nhanh. Với fibo(5) là 15 lời gọi, fibo(10) là 177,
fibo(20) đã là 21891, và fibo(40) vượt 300 triệu lời gọi. Mỗi lần tăng n thêm 1
thì khối lượng tính nhân lên khoảng 1,6 lần, tức là tăng theo hàm mũ. Trên máy tính
thông thường, fibo(45) chạy mất hàng chục giây, còn fibo(60) thì bạn có thể đi ngủ
rồi sáng mai nó vẫn chưa xong. Trong khi đó, tính tay dãy Fibonacci tới số thứ 60 chỉ
tốn 60 phép cộng.
Gốc rễ của sự lãng phí không nằm ở đệ quy nói chung, mà nằm ở chỗ bài toán này có các
bài con chồng lấn nhau. fibo(n-1) và fibo(n-2) cùng cần fibo(n-3), nên công
việc bị làm lại. Giai thừa thì khác hẳn: giaiThua(n) chỉ gọi một lời gọi con, không
có ai trùng với ai, nên đệ quy giai thừa tốn đúng n + 1 lời gọi (từ n xuống tới lời
gọi cơ sở giaiThua(0)), không hề lãng phí. Vậy
kết luận đúng không phải là "đệ quy chậm", mà là "đệ quy chậm khi các nhánh tính lại
cùng một thứ".
Xem chạy thêm: cây gọi fibo(4) và bài con chồng lấn
Bản trace ở đầu bài minh hoạ một chuỗi lời gọi thẳng của giaiThua(3). Trace này minh hoạ
một cơ chế khác: fibo gọi hai nhánh, và các nhánh cùng tính lại một bài con. Hãy để ý
fibo(2) bị tính hai lần, mỗi lần là một khung mới, máy không hề nhớ kết quả cũ.
1#include <stdio.h>2int fibo(int n) {3 if (n == 0) return 0;4 if (n == 1) return 1;5 return fibo(n - 1) + fibo(n - 2);6}7int main(void) {8 printf("%d\n", fibo(4));9 return 0;10}
Cách chữa đơn giản nhất là quay về vòng lặp, tính từ nhỏ lên lớn và giữ lại hai giá trị gần nhất:
#include <stdio.h>
// iterative Fibonacci: linear time, constant memory
long fiboLap(int n) {
if (n < 2) return n;
long truoc = 0, hien_tai = 1; // F(0) and F(1)
for (int i = 2; i <= n; i++) {
long moi = truoc + hien_tai; // next value from the last two
truoc = hien_tai; // shift the window forward
hien_tai = moi;
}
return hien_tai;
}
int main(void) {
printf("%ld\n", fiboLap(40)); // 102334155, instantly
return 0;
}
Bản này chỉ chạy n - 1 vòng, mỗi vòng một phép cộng, và chỉ giữ hai biến. Nó không tạo
khung nào trên ngăn xếp nên cũng không bao giờ tràn. Đổi lại, nó không còn phản ánh trực
tiếp định nghĩa toán học nữa; bạn phải tự nghĩ ra kỹ thuật cửa sổ trượt hai biến, một
bước nhảy mà bản đệ quy không đòi hỏi.
Đệ quy hay vòng lặp
Vì mọi hàm đệ quy đều viết lại được bằng vòng lặp và ngược lại, câu hỏi không phải cái nào đúng mà là cái nào phù hợp. Hãy cân nhắc theo bốn tiêu chí.
| tiêu chí | đệ quy | vòng lặp |
|---|---|---|
| bộ nhớ | tốn một khung ngăn xếp cho mỗi tầng | không tốn thêm |
| tốc độ | chậm hơn vì chi phí gọi hàm | nhanh hơn |
| độ dễ đọc | rất gọn khi định nghĩa mang tính tự lồng | dài hơn nhưng trực tiếp |
| rủi ro | tràn ngăn xếp khi quá sâu | lặp vô hạn nếu quên cập nhật |
Chọn đệ quy khi bài toán có cấu trúc tự lồng nhau mà bạn không biết trước độ sâu, và khi độ sâu ấy chắc chắn nhỏ: duyệt cây, quay lui, chia để trị kiểu sắp xếp trộn hay tìm kiếm nhị phân. Ở những bài đó, bản vòng lặp buộc bạn phải tự dựng lấy một ngăn xếp bằng tay, tức làm lại đúng cái việc máy đang làm hộ, và mã sẽ dài hơn hẳn.
Chọn vòng lặp khi bài toán vốn tuyến tính: cộng dồn, đếm, duyệt mảng, tính giai thừa hay Fibonacci. Ở những bài đó, đệ quy không cho bạn thêm gì về mặt diễn đạt mà lại lấy đi ngăn xếp và tốc độ. Một quy tắc thực hành dễ nhớ: nếu bạn viết được vòng lặp trong ba dòng mà không phải nghĩ lâu, đừng dùng đệ quy.
Bài tập thực hành
Bài tập 1: tổng các chữ số
Viết hàm int tongChuSo(int n) tính tổng các chữ số của một số nguyên dương bằng đệ quy.
Gợi ý: trường hợp cơ sở là khi n chỉ còn một chữ số.
Lời giải chi tiết
Khi n nhỏ hơn 10 thì chính nó là tổng (cơ sở). Ngược lại, lấy chữ số cuối bằng
n % 10, cộng với tổng chữ số của phần còn lại n / 10, đây là bước đệ quy với số nhỏ
hơn.
#include <stdio.h>
// sum of digits, recursively
int tongChuSo(int n) {
if (n < 10) // base case: single digit
return n;
return n % 10 + tongChuSo(n / 10); // last digit + rest
}
int main(void) {
printf("%d\n", tongChuSo(2025)); // 2 + 0 + 2 + 5 = 9
return 0;
}
Ý chính: mỗi bước bóc một chữ số nên n luôn nhỏ dần, chắc chắn tiến về trường hợp cơ sở.
Bài tập 2: ước chung lớn nhất theo Euclid
Viết hàm đệ quy int ucln(int a, int b) tìm ước chung lớn nhất theo thuật toán Euclid:
nếu b == 0 thì kết quả là a, ngược lại gọi ucln(b, a % b).
Lời giải chi tiết
Trường hợp cơ sở là b == 0, trả về a ngay. Bước đệ quy thay cặp (a, b) bằng
(b, a % b), số dư luôn nhỏ dần nên dãy chắc chắn dừng.
#include <stdio.h>
// Euclid's algorithm, recursive
int ucln(int a, int b) {
if (b == 0) // base case
return a;
return ucln(b, a % b); // recursive step
}
int main(void) {
printf("%d\n", ucln(48, 36)); // 12
return 0;
}
Ý chính: đệ quy phản ánh thẳng định nghĩa toán học của thuật toán Euclid, rất gọn.
Bài tập 3: giai thừa bằng đệ quy và bằng vòng lặp
Viết cả hai phiên bản tính giai thừa: một bằng đệ quy, một bằng vòng lặp for. So sánh
kết quả với cùng đầu vào và nhận xét về cách viết.
Lời giải chi tiết
Bản đệ quy bám theo định nghĩa n! = n * (n-1)!. Bản vòng lặp nhân dồn từ 1 tới n. Cả
hai cho cùng kết quả, nhưng bản vòng lặp không tạo nhiều khung trên ngăn xếp nên tránh
được nguy cơ tràn ngăn xếp khi n lớn.
#include <stdio.h>
long giaiThuaDeQuy(int n) {
if (n == 0) return 1; // base case
return n * giaiThuaDeQuy(n - 1); // recursive step
}
long giaiThuaLap(int n) {
long kq = 1;
for (int i = 2; i <= n; i++)
kq = kq * i; // multiply up from 2 to n
return kq;
}
int main(void) {
int n = 5;
printf("De quy: %ld\n", giaiThuaDeQuy(n)); // 120
printf("Vong lap: %ld\n", giaiThuaLap(n)); // 120
return 0;
}
Ý chính: đệ quy gọn gàng về ý tưởng, vòng lặp tiết kiệm ngăn xếp. Nhiều bài toán đệ quy có thể viết lại bằng vòng lặp và ngược lại.
Bài tập 4: đếm số lời gọi của Fibonacci đệ quy
Sửa hàm fibo để nó đếm xem mình được gọi tất cả bao nhiêu lần khi tính fibo(n). Chạy
thử với n bằng 5, 10, 20 rồi nhìn con số tăng thế nào. Gợi ý: dùng một biến toàn cục
làm bộ đếm, tăng nó ở dòng đầu tiên của hàm.
Lời giải chi tiết
Ta cần một biến sống lâu hơn từng lời gọi, vì mỗi khung có bản sao biến cục bộ riêng nên biến cục bộ không đếm chung được. Biến toàn cục làm được việc đó: nó nằm ngoài mọi khung, mọi lời gọi đều nhìn thấy cùng một ô nhớ. Đặt lệnh tăng ở dòng đầu tiên của hàm, trước cả kiểm tra cơ sở, để đếm được mọi lần hàm được vào, kể cả lần chỉ chạm cơ sở rồi trả về ngay.
#include <stdio.h>
long so_loi_goi = 0; // global counter, shared by every frame
int fibo(int n) {
so_loi_goi++; // count this entry
if (n == 0) return 0;
if (n == 1) return 1;
return fibo(n - 1) + fibo(n - 2);
}
int main(void) {
int cac_n[] = {5, 10, 20, 30};
for (int i = 0; i < 4; i++) {
so_loi_goi = 0; // reset before each measurement
int kq = fibo(cac_n[i]);
printf("fibo(%d) = %d, so loi goi = %ld\n",
cac_n[i], kq, so_loi_goi);
}
return 0;
}
Chạy chương trình, bạn sẽ thấy fibo(5) tốn 15 lời gọi, fibo(10) tốn 177, fibo(20)
tốn 21891, và fibo(30) vọt lên 2692537, tức gần 2,7 triệu. Từ n bằng 10 trở đi, cứ
tăng n thêm 10 thì con số nhân lên khoảng 120 lần. Đây là bằng chứng chạy được cho lời
khẳng định lý thuyết ở trên: khối lượng tính tăng theo hàm mũ chứ không theo n. Chú ý
dòng so_loi_goi = 0; đặt trước mỗi phép đo, nếu quên thì các con số sẽ cộng dồn vào
nhau và bạn đọc ra kết quả sai.
Muốn đi xa hơn, hãy thử sửa hàm để nó nhớ lại các giá trị đã tính bằng một mảng, tức
kỹ thuật ghi nhớ kết quả trung gian. Bạn sẽ thấy số lời gọi tụt xuống còn cỡ 2n, và
fibo(40) chạy tức thì thay vì mất hàng chục giây.
Tự kiểm tra
1) Vì sao mỗi hàm đệ quy phải có trường hợp cơ sở?
Trường hợp cơ sở là điểm dừng. Không có nó, hàm tự gọi mãi không ngừng, đẩy thêm khung mãi cho tới khi ngăn xếp đầy và chương trình tràn ngăn xếp.
2) Khi tính giaiThua(3), nhiều nhất có bao nhiêu khung trên ngăn xếp cùng lúc?
Bốn khung giaiThua: cho n = 3, 2, 1, 0, cộng thêm khung main. Khi gặp cơ sở tại
n = 0, các khung lần lượt được gỡ theo thứ tự ngược lại.
Câu hỏi tự kiểm
- 1Vì sao bản đệ quy của Fibonacci lại chậm thảm hại với n lớn?
- 2Gọi giaiThua(-1) với trường hợp cơ sở là if (n == 0) return 1; thì điều gì xảy ra?
- 3Số khung cùng tồn tại trên ngăn xếp tại một thời điểm bằng đại lượng nào?
- 4Tính giaiThua(n) bằng đệ quy tốn bao nhiêu lời gọi hàm?
Tóm tắt bài học
Một hàm đệ quy gồm đúng hai phần: trường hợp cơ sở trả lời ngay không gọi tiếp, và bước truy hồi gọi lại chính nó với dữ liệu nhỏ hơn. Khi viết, hãy trả lời ba câu hỏi theo thứ tự: bài nhỏ nhất là bài nào, ghép lời giải con vào ra sao, và dữ liệu có chắc chắn tiến về cơ sở trên mọi đầu vào hợp lệ hay không. Đừng cố hình dung cả chuỗi lời gọi trong đầu, hãy tin lời gọi con trả về đúng.
Về cơ chế, mỗi lời gọi chưa xong chiếm một khung trên ngăn xếp, chứa bản sao tham số riêng và địa chỉ trở về. Khung cha không được giải phóng khi gọi con, nó đóng băng chờ, nên số khung tồn tại cùng lúc bằng độ sâu đệ quy. Ngăn xếp chỉ có vài megabyte, đệ quy quá sâu hoặc không có điểm dừng sẽ làm chương trình chết đột ngột mà không báo lỗi tử tế.
Về chi phí, đệ quy không xấu, nhưng nó chậm thảm hại khi các nhánh cùng tính lại một
thứ. Giai thừa gọi một nhánh nên tốn đúng n + 1 lời gọi. Fibonacci gọi hai nhánh chồng lấn
nhau nên số lời gọi tăng theo hàm mũ, và bản vòng lặp với hai biến trượt nhanh hơn nó
hàng triệu lần. Quy tắc chọn: dùng đệ quy cho cấu trúc tự lồng và độ sâu nhỏ, dùng vòng
lặp cho bài toán tuyến tính.
Đệ quy chia bài lớn thành bài nhỏ cùng dạng, dừng tại trường hợp cơ sở. Mỗi lời gọi tạo một khung trên ngăn xếp; khi tới cơ sở, các khung trả giá trị ngược lên rồi lần lượt được gỡ. Đệ quy quá sâu hoặc thiếu cơ sở sẽ gây tràn ngăn xếp.