Tư duy tính toán và giải quyết vấn đề

A tìm kiếm (search) tìm một giá trị mục tiêu (target value) trong một tập hợp (thường là một mảng - array) và trả về vị trí của nó, hoặc thông báo "không tìm thấy".

Tìm kiếm tuyến tính

A tìm kiếm tuyến tính (linear search) duyệt từ đầu đến cuối, so sánh từng phần tử với giá trị mục tiêu:

FOR i ← 1 TO n
    IF A[i] = target THEN
        RETURN i
    ENDIF
NEXT i
RETURN -1   // not found

Không cần chuẩn bị trước, nên nó hoạt động trên mọi danh sách. Trường hợp xấu nhất O($n$) (giá trị mục tiêu nằm ở cuối hoặc không tồn tại); trường hợp tốt nhất 1 phép so sánh. Sử dụng cho dữ liệu không sắp xếp hoặc danh sách nhỏ. (Giá trị trả về -1 là một giá trịsentinel — một vị trí không thể có nghĩa là "không tìm thấy"; người gọi kiểm tra IF result = -1.)

Phiên bản kỳ thi. Bài 3 yêu cầu bạn hoàn thành một thuật toán tìm kiếm tuyến tính được viết với biến cờ và vòng lặp WHILE, và Bài 4 yêu cầu viết một hàm trả về chỉ số hoặc một đếm. Cả hai đều trông giống như thế này:

FUNCTION LinearSearch(Data : ARRAY OF INTEGER, Target : INTEGER) RETURNS INTEGER
    DECLARE Index, Count : INTEGER
    Count ← 0
    FOR Index ← 1 TO 100
        IF Data[Index] = Target THEN
            Count ← Count + 1
        ENDIF
    NEXT Index
    RETURN Count          // how many times Target occurs; 0 means not found
ENDFUNCTION

Để dừng lại ở trùng khớp đầu tiên thay vì vậy, hãy sử dụng vòng lặp WHILE Index <= 100 AND NOT Found thiết lập Found ← TRUE và ghi nhớ chỉ số. Điểm số dành cho vòng lặp qua mọi phần tử, phép so sánh, và những gì được trả về khi giá trị không tồn tại.

Tìm kiếm nhị phân

A tìm kiếm nhị phân (binary search) yêu cầu dữ liệu phải được sắp xếp. Xem xét phần tử ở giữa; nếu đó là giá trị mục tiêu thì xong; nếu giá trị mục tiêu nhỏ hơn, tìm kiếm nửa trái, ngược lại tìm kiếm nửa phải — thu hẹp phạm vi tìm kiếm đi một nửa mỗi bước:

low ← 1
high ← n
WHILE low <= high DO
    mid ← (low + high) DIV 2
    IF A[mid] = target THEN
        RETURN mid
    ENDIF
    IF A[mid] < target THEN
        low ← mid + 1
    ELSE
        high ← mid - 1
    ENDIF
ENDWHILE
RETURN -1

Trường hợp xấu nhất O($\log_{2} n$) — đối với một triệu phần tử, khoảng 20 phép so sánh. Nhanh hơn nhiều so với tìm kiếm tuyến tính trên mảng lớn đã sắp xếp, nhưng bạn phải sắp xếp trước (một chi phí một lần O($n \log n$)), đáng giá nếu bạn tìm kiếm nhiều lần.

"Nêu điều kiện cần thiết cho tìm kiếm nhị phân." Dữ liệu phải được sắp xếp (tăng dần hoặc giảm dần, dựa trên khóa đang tìm kiếm). "Mô tả cách thực hiện tìm kiếm nhị phân" (ba điểm): (1) tìm phần tử giữa của danh sách (hoặc phạm vi hiện tại) và so sánh nó với giá trị mục tiêu; (2) nếu trùng khớp, tìm kiếm kết thúc; nếu giá trị mục tiêu nhỏ hơn, lặp lại trên nửa dưới, nếu lớn hơn, trên nửa trên; (3) tiếp tục chia đôi phạm vi cho đến khi tìm thấy phần tử hoặc phạm vi rỗng, có nghĩa là nó không tồn tại.

Phiên bản kỳ thi, với các cận và một biến cờ, là thứ bạn phải sao chép lại khi được yêu cầu hoàn thành thuật toán:

DECLARE Lower, Upper, Mid : INTEGER
DECLARE Found : BOOLEAN
Lower ← 0
Upper ← 99
Found ← FALSE
WHILE Lower <= Upper AND NOT Found
    Mid ← (Lower + Upper) DIV 2
    IF Names[Mid] = Target THEN
        Found ← TRUE
    ELSE
        IF Names[Mid] < Target THEN
            Lower ← Mid + 1
        ELSE
            Upper ← Mid - 1
        ENDIF
    ENDIF
ENDWHILE
IF Found THEN
    OUTPUT Mid
ELSE
    OUTPUT "Not found"
ENDIF

"Giải thích cách hiệu suất thay đổi theo số lượng phần tử." Mỗi phép so sánh chia đôi số lượng phần tử còn lại, do đó số lượng tối đa các phép so sánh là khoảng $\log_{2} n$: gấp đôi kích thước danh sách chỉ thêm một phép so sánh nữa. Đây là O($\log n$). "So sánh tìm kiếm tuyến tính và tìm kiếm nhị phân": tìm kiếm tuyến tính cần tối đa $n$ phép so sánh (O($n$)) và, trung bình, nửa số đó, nhưng hoạt động trên dữ liệu không sắp xếp; tìm kiếm nhị phân cần tối đa $\log_{2} n$ (O($\log n$)) và nhanh hơn rất nhiều đối với danh sách lớn, nhưng dữ liệu trước tiên phải được sắp xếp và nó phải cho phép truy cập trực tiếp đến phần tử ở giữa (mảng, không phải danh sách liên kết). Đối với $1000$ phần tử: $1000$ so với $10$ phép so sánh.

Sắp xếp bọt

A sắp xếp bong bóng (bubble sort) nhiều lần duyệt qua mảng, hoán đổi các cặp phần tử liền kề bị sai thứ tự, khiến phần tử lớn nhất "bọt" lên cuối mảng sau mỗi lần duyệt:

FOR pass ← 1 TO n - 1
    swapped ← FALSE
    FOR i ← 1 TO n - pass
        IF A[i] > A[i + 1] THEN
            temp ← A[i]
            A[i] ← A[i + 1]
            A[i + 1] ← temp
            swapped ← TRUE
        ENDIF
    NEXT i
    IF swapped = FALSE THEN      // already sorted
        EXIT FOR
    ENDIF
NEXT pass

Trường hợp tốt nhất O($n$) (đã sắp xếp, với việc thoát sớm); trung bình/xấu nhất O($n^{2}$). Đơn giản nhưng chậm đối với các $n$ lớn.

Sắp xếp chèn

A sắp xếp chèn (insertion sort) xây dựng một tiền tố đã sắp xếp từ phía trái, chèn từng phần tử mới vào đúng vị trí bằng cách dịch chuyển các phần tử lớn hơn sang phải:

FOR i ← 2 TO n
    key ← A[i]
    j ← i - 1
    WHILE j >= 1 AND A[j] > key DO
        A[j + 1] ← A[j]
        j ← j - 1
    ENDWHILE
    A[j + 1] ← key
NEXT i

Trường hợp tốt nhất O($n$) (đã sắp xếp); xấu nhất O($n^{2}$). Tốt cho các mảng nhỏ hoặc gần như đã sắp xếp. Nó sắp xếp ngay tại chỗ và là ổn định (giữ nguyên thứ tự của các phần tử bằng nhau).

Theo dõi quá trình sắp xếp

Một nhiệm vụ thường gặp là hiển thị mảng sau mỗi lần lặp ngoài. Với [D, T, H, R] sắp xếp chèn: lần lặp 1 (chìa khóa T) không thay đổi; lần lặp 2 (chìa khóa H) → [D, H, T, R]; lần lặp 3 (chìa khóa R) → [D, H, R, T].

Viết thuật toán sắp xếp từ đầu. "Viết mã giả để sắp xếp DataArray[1:1000] theo thứ tự tăng dần" được trả lời bởi một thuật toán sắp xếp bọt đầy đủ với biến cờ thoát sớm, hoặc thuật toán sắp xếp chèn, được khai báo và thụt vào trong; cả hai đều đạt điểm tối đa nếu nó hoạt động cho mọi đầu vào:

DECLARE Pass, Index, Temp : INTEGER
DECLARE Swapped : BOOLEAN
Pass ← 1
REPEAT
    Swapped ← FALSE
    FOR Index ← 1 TO 1000 - Pass
        IF DataArray[Index] > DataArray[Index + 1] THEN
            Temp ← DataArray[Index]
            DataArray[Index] ← DataArray[Index + 1]
            DataArray[Index + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT Index
    Pass ← Pass + 1
UNTIL Swapped = FALSE OR Pass = 1000

Đối với thứ tự giảm dần, thay > bằng <; để sắp xếp các bản ghi hoặc mảng 2D theo một trường, hãy so sánh trường đó nhưng hoán đổi toàn bộ bản ghi (hoặc mọi cột). Được yêu cầu viết một thuật toán sắp xếp chèn "thực hiện cùng một nhiệm vụ" như một thuật toán sắp xếp bọt đã cho, hãy giữ nguyên tên mảng và hướng sắp xếp và sao chép lại thuật toán sắp xếp chèn ở trên với phép so sánh đảo ngược nếu thứ tự là giảm dần.

"Mô tả hai cách mà hiệu suất của một thuật toán sắp xếp bị ảnh hưởng bởi dữ liệu" (hai điểm). (1) Số lượng phần tử: một thuật toán $O(n^{2})$ mất gấp bốn lần thời gian khi số lượng phần tử tăng gấp đôi. (2) Mức độ đã được sắp xếp sẵn của dữ liệu: bubble sort có cờ, hoặc insertion sort, sẽ hoàn thành trong một lượt duyệt duy nhất trên dữ liệu đã được sắp xếp ($O(n)$) và thực hiện nhiều công việc nhất đối với dữ liệu theo thứ tự ngược; số lần hoán đổi phụ thuộc vào số cặp phần tử không đúng thứ tự. (Cũng chấp nhận: phạm vi hoặc số giá trị trùng lặp, và liệu các phần tử có phải là bản ghi lớn tốn kém khi di chuyển hay không.) Bubble sort và insertion sort đều có độ phức tạp O($n^{2}$) trong trường hợp xấu nhất và trung bình, và O($n$) ở trường hợp tốt nhất; quicksort và merge sort có độ phức tạp O($n \log n$), đó là lý do tại sao chúng được sử dụng cho dữ liệu lớn.

Các Abstract Data Types (ADTs) từ Chủ đề 10 xuất hiện bên trong nhiều thuật toán: một ngăn xếp điều khiển việc duyệt theo chiều sâu và chức năng hoàn tác; một hàng đợi điều khiển việc duyệt theo chiều rộng và thứ tự in ấn; một danh sách liên kết cho phép dữ liệu mở rộng và thu gọn.

ADTs có thể được xây dựng từ các ADTs khác, không chỉ từ mảng: một hàng đợi từ hai ngăn xếp; một ngăn xếp từ danh sách liên kết (push = thêm đầu nút); một hàng đợi từ danh sách liên kết với con trỏ đầu và cuối; một cây nhị phân từ các nút có hai con trỏ con; một từ điển lưu trữ cặp key→value (thường trên bảng hash). Xếp lớp như vậy tách biệt các mối quan tâm — thuật toán sử dụng ADT không cần biết nó được xây dựng như thế nào.

Các ADTs mà đề thi yêu cầu bạn mô tả và triển khai

Ngăn xếp (lối vào cuối, lối ra đầu): các phần tử được thêm (pushed) và lấy ra (popped) ở cùng một đầu, đỉnh; một con trỏ TopOfStack giữ chỉ số của phần tử đỉnh. Được triển khai bằng mảng và con trỏ đơn lẻ này: push kiểm tra ngăn xếp chưa đầy, tăng con trỏ và lưu phần tử; pop kiểm tra chưa rỗng, trả về phần tử đỉnh và giảm con trỏ.

FUNCTION Push(Item : INTEGER) RETURNS BOOLEAN
    IF TopOfStack = 9 THEN      // full (array 0 to 9)
        RETURN FALSE
    ENDIF
    TopOfStack ← TopOfStack + 1
    StackData[TopOfStack] ← Item
    RETURN TRUE
ENDFUNCTION
FUNCTION Pop() RETURNS INTEGER
    IF TopOfStack = -1 THEN      // empty
        RETURN -1
    ENDIF
    TopOfStack ← TopOfStack - 1
    RETURN StackData[TopOfStack + 1]
ENDFUNCTION

Hàng đợi (lối vào đầu, lối ra đầu): các phần tử gia nhập ở cuối (enqueue) và rời đi từ đầu (dequeue); hai con trỏ và một biến đếm. Trong hàng đợi tuyến tính, con trỏ đầu bò dọc theo mảng cho đến khi không gian ở đầu bị lãng phí; một hàng đợi vòng làm tròn cả hai con trỏ với MOD, vì vậy mọi ô nhớ đều được tái sử dụng.

FUNCTION Enqueue(Item : STRING) RETURNS BOOLEAN
    IF Count = 6 THEN      // full
        RETURN FALSE
    ENDIF
    Rear ← (Rear + 1) MOD 6
    QueueArray[Rear] ← Item
    Count ← Count + 1
    RETURN TRUE
ENDFUNCTION
FUNCTION Dequeue() RETURNS STRING
    IF Count = 0 THEN      // empty
        RETURN ""
    ENDIF
    DECLARE Item : STRING
    Item ← QueueArray[Front]
    Front ← (Front + 1) MOD 6
    Count ← Count - 1
    RETURN Item
ENDFUNCTION

Danh sách liên kết: một chuỗi các nút, mỗi nút chứa một phần tử dữ liệu và một con trỏ trỏ đến nút tiếp theo; một con trỏ bắt đầu chỉ nút đầu tiên và một con trỏ null (0 hoặc $-1$) kết thúc danh sách. Trong triển khai bằng mảng, hai mảng song song chứa dữ liệu và các con trỏ, và các ô trống được nối thành mảng tự do (free list) để việc chèn biết nơi đặt nút mới.

FUNCTION FindInList(Target : STRING) RETURNS INTEGER   // index, or 0 if absent
    DECLARE Current : INTEGER
    Current ← Start
    WHILE Current <> 0
        IF Data[Current] = Target THEN
            RETURN Current
        ENDIF
        Current ← Pointer[Current]
    ENDWHILE
    RETURN 0
ENDFUNCTION

Để chèn vào danh sách đã sắp xếp: lấy ô trống đầu tiên (NewNode ← FreeList, FreeList ← Pointer[FreeList]), lưu phần tử, sau đó duyệt danh sách với con trỏ Previous và Current cho đến khi Data[Current] > Item hoặc hết danh sách; thiết lập Pointer[NewNode] ← Current và Pointer[Previous] ← NewNode (hoặc Start ← NewNode nếu nó vào đầu). Để xóa, liên kết lại nút trước vượt qua nút bị xóa và trả ô về mảng tự do.

Cây nhị phân: một nút gốc, mỗi nút chứa dữ liệu, một con trỏ trái trỏ đến cây con có giá trị nhỏ hơn và một con trỏ phải trỏ đến cây con có giá trị lớn hơn. Triển khai dưới dạng mảng 2D (hoặc ba mảng 1D) Tree[Index, 0..2] cho con trỏ trái, dữ liệu, con trỏ phải, với con trỏ gốc và con trỏ tự do tiếp theo.

FUNCTION FindInTree(Target : INTEGER) RETURNS INTEGER   // index, or -1
    DECLARE Current : INTEGER
    Current ← Root
    WHILE Current <> -1
        IF Tree[Current, 1] = Target THEN
            RETURN Current
        ENDIF
        IF Target < Tree[Current, 1] THEN
            Current ← Tree[Current, 0]      // go left
        ELSE
            Current ← Tree[Current, 2]      // go right
        ENDIF
    ENDWHILE
    RETURN -1
ENDFUNCTION

Để chèn: lưu phần tử vào nút tự do tiếp theo với cả hai con trỏ $-1$; nếu cây rỗng thì tạo nó làm nút gốc; nếu không thì duyệt xuống từ nút gốc, đi sang trái hoặc phải dựa trên so sánh, cho đến khi con trỏ mà bạn sẽ theo đuổi là $-1$, và thiết lập con trỏ đó trỏ đến nút mới. Một ADT từ một ADT khác: một ngăn xếp là một danh sách liên kết nơi push và pop đều hoạt động ở đầu; một hàng đợi là một danh sách liên kết với con trỏ bắt đầu và con trỏ cuối; một hàng đợi có thể được tạo từ hai ngăn xếp (push vào cái này, pop từ cái kia, di chuyển tất cả sang khi cái kia rỗng); các nút của cây nhị phân là bản ghi hoặc đối tượng được liên kết bởi các con trỏ, vì vậy nó được xây dựng từ cấu trúc danh sách liên kết. Nói xem các thao tác của ADT mới ánh xạ lên các thao tác nào của ADT cũ.

Độ phức tạp về thời gian

Độ phức tạp thời gian là cách thời gian chạy tăng lên theo kích thước đầu vào $n$, được viết dưới ký hiệu Big-O (hạng mục chi phối): O(1) hằng số, O($\log n$) tìm kiếm nhị phân, O($n$) tìm kiếm tuyến tính, O($n \log n$) các thuật toán sắp xếp tốt, O($n^{2}$) sắp xếp nổi/bubble và sắp xếp chèn/insertion. Hạng mục nhỏ hơn thì tốt hơn ở quy mô lớn, ngay cả khi một thuật toán khác nhanh hơn với dữ liệu nhỏ $n$.

Để minh họa cụ thể: để sắp xếp một triệu mục, một thuật toán $O(n \log n)$ sẽ hoàn thành trong một phần nhỏ của một giây, trong khi một thuật toán $O(n^{2})$ có thể mất vài phút.

Ví dụ đã giải. Một danh sách đã sắp xếp chứa $1000$ mục. Mỗi phép tìm kiếm cần bao nhiêu phép so sánh trong trường hợp xấu nhất?

Tìm kiếm tuyến tính kiểm tra từng mục một, vì vậy nó có thể cần tới $1000$ phép so sánh — đây là $O(n)$. Tìm kiếm nhị phân chia đôi danh sách mỗi bước, nên chỉ cần tối đa $\lceil \log_2 1000 \rceil = 10$ phép so sánh — đây là $O(\log n)$. Gấp đôi danh sách lên $2000$ mục chỉ thêm một phép so sánh cho tìm kiếm nhị phân, nhưng có thể thêm tới $1000$ nữa cho tìm kiếm tuyến tính — đó là lý do hạng mục tăng trưởng, chứ không phải tốc độ tuyệt đối, mới quyết định người chiến thắng ở quy mô lớn.

Mô tả hạng mục tăng trưởng. O(1): thời gian là hằng số, không phụ thuộc vào số lượng mục (thêm vào stack, đọc phần tử mảng). O($\log n$): thời gian tăng theo logarit của số lượng mục, vì vậy gấp đôi dữ liệu chỉ thêm một bước cố định (tìm kiếm nhị phân). O($n$): thời gian tăng tỷ lệ thuận với số lượng mục (tìm kiếm tuyến tính, một lần duyệt qua danh sách). O($n \log n$): kém hơn tuyến tính một chút (thuật toán sắp xếp hiệu quả). O($n^{2}$): thời gian tăng theo bình phương của số lượng mục, vì vậy gấp đôi dữ liệu làm bốn lần thời gian (sắp xếp nổi và sắp xếp chèn). "Nêu Big O của tìm kiếm nhị phân trên Names[0:99]" là câu trả lời $O(\log n)$, và "mô tả ý nghĩa của nó" như trên; Big O đo lường cách thời gian hoặc bộ nhớ phát triển theo tỷ lệ, chứ không phải thời gian thực tế.

Độ phức tạp không gian

Độ phức tạp không gian là bộ nhớ bổ sung cần thiết. Sắp xếp nổi và sắp xếp chèn sử dụng O(1) bộ nhớ phụ (ngay tại chỗ); sắp xếp hợp nhất sử dụng O($n$); đệ quy sử dụng bộ nhớ stack tương ứng với độ sâu của nó. Thường tồn tại sự đánh đổi giữa thời gian và bộ nhớ.

Các tiêu chí khác

Tính đơn giản (dễ mã hóa và bảo trì), tính ổn định, và tính thích nghi (nhanh hơn trên dữ liệu gần như đã sắp xếp). Thuật toán phù hợp phụ thuộc vào dữ liệu và các ràng buộc.

Thuật toán đệ quy sử dụng đệ quy: routine gọi chính nó với phiên bản nhỏ hơn của cùng một vấn đề, cho đến khi một trường hợp cơ sở kết thúc chuỗi. Nó có hai phần: trường hợp cơ sở (nhỏ đủ để giải trực tiếp — nếu không có nó thì đệ quy sẽ không bao giờ dừng) và trường hợp đệ quy (giảm đầu vào và gọi chính nó lại).

Giả thừa:

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
    IF n = 0 OR n = 1 THEN
        RETURN 1
    ELSE
        RETURN n * Factorial(n - 1)
    ENDIF
ENDFUNCTION

Đệ quy tự nhiên cho các vấn đề tự tương đồng: cây, chia để trị (tìm kiếm nhị phân, sắp xếp hợp nhất), và dữ liệu lồng nhau. Khi nó không phù hợp, vòng lặp thường sạch sẽ hơn.

"Mô tả ý nghĩa của đệ quy (hai điểm).** Một hàm hoặc thủ tục được định nghĩa dựa trên chính nó: nó gọi chính nó từ bên trong thân của nó, với một phiên bản nhỏ hơn của vấn đề mỗi lần, cho đến khi đạt được trường hợp cơ sở. "Nêu ba đặc điểm thiết yếu của đệ quy": (1) một trường hợp cơ sở (điều kiện dừng) trả về giá trị mà không có cuộc gọi nào thêm; (2) một trường hợp tổng quát nơi routine gọi chính nó; (3) mỗi cuộc gọi di chuyển vấn đề gần hơn với trường hợp cơ sở (tham số bị giảm), để đệ quy kết thúc. Một số sơ đồ thêm: các giá trị được trả về khi các cuộc gọi pop ra.

"Mô tả khi nào việc sử dụng đệ quy có lợi ích, và đưa ra ví dụ." Khi vấn đề được định nghĩa tự nhiên theo các phiên bản nhỏ hơn của chính nó, sao cho giải pháp đệ quy ngắn gọn, rõ ràng và gần với định nghĩa toán học hơn so với việc sử dụng vòng lặp: giả thừa hoặc số Fibonacci, tìm kiếm nhị phân, duyệt cây nhị phân, sắp xếp hợp nhất hoặc sắp xếp nhanh, và xử lý cấu trúc lồng nhau như thư mục nằm trong thư mục. Đây là lựa chọn kém khi độ sâu lớn (stack có thể tràn) hoặc khi cùng một bài toán con được tính toán nhiều lần (Fibonacci ngây thơ).

Theo dõi một cuộc gọi đệ quy

Đối với Factorial(4): các cuộc gọi đi xuống đến Factorial(1)=1, sau đó pop ra nhân ngược lên: 2*1=2, 3*2=6, 4*6=24. Kết quả cuối cùng 24. Theo dõi từng cuộc gọi đang chờ trên stack.

Ví dụ đã giải. Hàm dưới đây được đưa ra mà không có giải thích. Hãy theo dõi Unknown(3, 5) và nêu đầu ra cũng như giá trị trả về.

FUNCTION Unknown(BYVAL X, BYVAL Y : INTEGER) RETURNS INTEGER
    IF X < Y THEN
        OUTPUT X + Y
        RETURN Unknown(X + 1, Y - 1) + 1
    ELSE
        RETURN 0
    ENDIF
ENDFUNCTION

Gọi 1: $X = 3, Y = 5$: $3 < 5$, output 8, gọi Unknown(4, 4). Gọi 2: $4 < 4$ là sai, return 0. Pop ra: gọi 1 trả về $0 + 1 = 1$. Output 8, giá trị trả về 1. Viết quá trình theo dõi dưới dạng bảng với mỗi hàng cho một cuộc gọi (tham số, điều kiện, output, nó trả về gì), và thực hiện các lần trả về từ cuộc gọi sâu nhất lên trên: đó chính là quá trình pop ra mà đáp án chấm điểm mong đợi.

Ví dụ có lời giải (Fibonacci). Fib(n) trả về n khi n < 2, ngược lại trả về Fib(n - 1) + Fib(n - 2). Tìm Fib(5).

Fib(5) = Fib(4) + Fib(3); Fib(4) = Fib(3) + Fib(2); Fib(3) = Fib(2) + Fib(1); Fib(2) = Fib(1) + Fib(0) = 1 + 0 = 1. Vậy Fib(3) = 1 + 1 = 2, Fib(4) = 2 + 1 = 3, Fib(5) = 3 + 2 = 5. Trường hợp cơ sở được đạt được rất nhiều lần (Fib(2) được tính ba lần), đó là lý do phiên bản này chậm: nó thực hiện 15 cuộc gọi cho $n = 5$ và xấp xỉ gấp đôi số cuộc gọi cho mỗi lần tăng $n$.

Biến đổi đệ quy thành lặp. Mọi thủ tục đệ quy đều có thể được viết lại bằng vòng lặp, sử dụng ít bộ nhớ hơn và nhanh hơn: giữ kết quả đang tính và lặp từ trường cơ sở lên trên. Factorial dưới dạng vòng lặp:

FUNCTION Factorial(N : INTEGER) RETURNS INTEGER
    DECLARE Result, Count : INTEGER
    Result ← 1
    FOR Count ← 2 TO N
        Result ← Result * Count
    NEXT Count
    RETURN Result
ENDFUNCTION

Khi được yêu cầu chuyển đổi thuật toán sắp xếp chèn hoặc tìm kiếm đệ quy sang dạng lặp, hãy thay thế lời gọi tự thân bằng vòng lặp trên chỉ số mà đệ quy đã duyệt qua, và biến đổi trường cơ sở thành điều kiện dừng của vòng lặp.

Rủi ro

• đệ quy vô hạn nếu bỏ sót trường cơ sở — gây lỗi vượt quá ngàn (stack overflow) với ngàn tràn.
• tiêu thụ bộ nhớ cao đối với đệ quy sâu.
• chậm nếu thực hiện công việc trùng lặp (Fibonacci thô sơ là hàm mũ — hãy dùng vòng lặp hoặc ghi nhớ/ memoisation).

Đệ quy cần mỗi lời gọi phải có bản sao riêng của tham số và biến cục bộ của nó. Trình biên dịch lưu các thứ này trên ngàn gọi. Với mỗi lời gọi, nó đẩy một khung ngàn chứa tham số, biến cục bộ và địa chỉ trả về (nơi tiếp tục trong hàm gọi). Khi hàm trả về, giá trị trả về được giao lại, khung bị loại bỏ, và điều khiển quay lại địa chỉ trả về.

Vì mỗi lời gọi có khung riêng, các lời gọi đệ quy không ghi đè lên biến của nhau. Ngàn có thể phát triển lớn khi đệ quy sâu, đó là lý do tại sao đệ quy quá sâu có thể khiến ngàn tràn. Đây cũng chính là cơ chế gọi và trả về được sử dụng cho các lời gọi thông thường (không đệ quy) — không có "cơ chế đặc biệt nào cho đệ quy".

"Giải thích vì sao ngàn phù hợp để triển khai đệ quy (ba điểm).** Mỗi lời gọi đệ quy phải lưu địa chỉ trả về, tham số và biến cục bộ của nó, và các lời gọi được hoàn tất theo thứ tự ngược so với thứ tự chúng được thực hiện (lời gọi cuối cùng được thực hiện là lời đầu tiên hoàn tất), đúng như hành vi cuối vào trước ra (LIFO) của ngàn: mỗi lời gọi mới đẩy một khung, và mỗi lần trả về loại bỏ khung gần đây nhất, khôi phục trạng thái của hàm gọi và chỉ dẫn nơi nó tiếp tục. Đây là công việc của trình biên dịch khi dịch mã đệ quy: nó tạo ra việc đẩy khung ngàn ở mọi lời gọi và việc loại bỏ ở mọi lần trả về, và các khung được mở rộng ra khi các kết quả được trả về.

Câu hỏi định nghĩa được chấm dựa trên văn phong cố định. Hãy học thuộc những định nghĩa này và chỉ đưa ra một đáp án duy nhất.

• Tìm kiếm: tìm kiếm tuyến tính không cần thứ tự và có độ phức tạp O($n$); tìm kiếm nhị phân cần mảng đã sắp xếp, giảm một nửa mỗi lần và có độ phức tạp O($\log n$). Hãy thuộc lòng cả hai thuật toán, bao gồm cả cận và cờ báo hiệu.
• Sắp xếp: sắp xếp bong bóng với cờ hoán đổi, sắp xếp chèn với khóa di chuyển các mục lớn hơn sang phải; cả hai đều là O($n^{2}$)finished worst, O($n$)finished best on sorted data. Hiệu suất phụ thuộc vào số lượng mục và mức độ đã sắp xếp của chúng.
• Triển khai ADT là quản lý con trỏ: con trỏ đỉnh; front, rear và count với MOD; start, con trỏ và danh sách trống; root với con trỏ trái và phải. Luôn kiểm tra trạng thái đầy và rỗng.
• Big O nói về sự mở rộng: hằng số, logarit, tuyến tính, bình phương. Hãy nói "gấp đôi dữ liệu thì thêm một phép so sánh" cho tìm kiếm nhị phân.
• Đệ quy: trường cơ sở, trường tổng quát, tiến tới trường cơ sở; có lợi khi bài toán được định nghĩa theo chính nó; một ngàn giữ các địa chỉ trả về và biến vì các lời gọi trả về theo thứ tự ngược. Theo dõi bằng bảng và mở rộng ngàn từ lời gọi sâu nhất.

Lỗi thường gặp

• Sử dụng tìm kiếm nhị phân trên dữ liệu chưa sắp xếp, hoặc trên danh sách liên kết; và đặt Lower ← Mid thay vì Mid + 1, sẽ tạo vòng lặp vô tận.
• Vòng lặp bên trong sắp xếp bong bóng chạy đến hết mảng mỗi lượt duyệt, hoặc hoán đổi mà không dùng biến tạm.
• Một lệnh push hoặc enqueue không kiểm tra trạng thái đầy, hoặc pop hoặc dequeue không kiểm tra trạng thái rỗng.
• Di chuyển con trỏ front của hàng đợi mà không dùng MOD trong hàng đợi tròn, hoặc coi front = rear luôn luôn có nghĩa là rỗng.
• Chèn vào danh sách liên kết bằng cách di chuyển nội dung mảng; chỉ có các con trỏ thay đổi.
• Một hàm đệ quy không có trường cơ sở, hoặc một hàm mà lời gọi đệ quy của nó không thu nhỏ bài toán.
• Vẽ lại một lời gọi đệ quy nhưng quên thêm công việc còn dang dở trên đường quay ngược trở lại.
• Trả lời "tại sao dùng stack" với "vì nó nhanh"; lý do thực sự là thứ tự last-in-first-out (lối vào sau, ra trước) của các phép trả về.