Đệ quy

Đệ quy là phương pháp lập trình được dùng trong tin học trong đó có một hàm hoặc thủ tục gọi chính nó.

Các bài toán điển hình khi học về đệ quy:

·        Bài toán tháp hà nội.

·        Bài toán tính giai thừa.

·        Bài toán tính số fibonaci.

Tuy nhiên khi sử dụng đệ quy chúng ta rất tốn bộ nhớ và thời gian thực hiện chương trình.

Trong hàm đệ quy chúng ta bao giờ cũng có một điều kiện để dừng đệ quy.

Bài toán tính giai thừa.

Trong toán học N! = 1.2.3…N, là tích N số nguyên liên tiếp. Đọc là N giai thừa.

Quy ước 0! = 1.

Chúng ta thấy N! = 1.2.3….(N-1).N = (N-1)!N. Do đó chúng ta tính N! thì chúng ta tính (N-1)! rồi lấy kết quả đó nhân với N.

Chúng ta thiết kê một hàm tính giai thừa rất đơn giản như sau, code sau được viết trên free pascal.

program giaithua_dequy;

var

    n: longint;

(*Chương trình con tính giai thừa*)

function giaithua(m:longint):longint;

begin

(*

    writeln('m=',m);

    readln;

*)   

    if((m = 0) or (m = 1)) then giaithua := 1 (* Điều kiện để dừng đệ quy *)

    else

        giaithua := giaithua(m - 1) * m;           (* Gọi lại hàm giai thừa tính (m-1)! *)

end;

begin

    writeln(giaithua(5));

    readln;

end.

Bài toán dãy fibonaci: Dãy Fibonaci định nghĩa như sau:

F1 = 1, F2 = 1, Fn = Fn-1 + Fn-2.

Như vậy các số hạng đầu tiên của dãy như sau:

F3 = F2 + F1 = 1 + 1 = 2

F4 = F3 + F2 = 2 + 1 = 3

…..

Vấn đề đặt ra ta cần lập trình như thế nào?

Đoạn code sau được lập trình trên IDE free pascal.

program fibonaci;

function fibo(m: longint):longint;

begin

    (* điều kiện dừng đệ quy *)

    if((m = 1)or(m = 2)) then fibo := 1

    else

        fibo := fibo(m - 1) + fibo(m - 2);

end;

begin

    writeln(fibo(1));

    writeln(fibo(2));

    writeln(fibo(3));

    writeln(fibo(4));

    readln;

end.

Bài toán tháp Hà Nội:

Gồm một bộ các đĩa kích thước khác nhau, có lỗ ở giữa nằm xuyên trên ba cái cọc.

Giả sử có ba cái cọc A, B, C. Ban đầu các đĩa nằm trên cọc A (cọc nguồn), cần di chuyển tất cả cả các đĩa sang cọc C (cọc đích), với cọc B làm cọc trung gian theo quy tắc sau:

·        Mỗi lần chỉ di chuyển một cọc.

·        Một đĩa chỉ được đặt trên một đĩa có kích thước lớn hơn.

Thuật toán giải bài toán này theo đệ quy như sau:

·        Để di chuyển được N đĩa từ cọc A sang cọc C thì ta cần di chuyển N-1 đĩa sang cọc trung gian B.

·        Như vậy ta chỉ cần di chuyển 1 đĩa còn lại trên cọc A sang cọc C.

·        Sau đó chuyển N-1 đĩa còn lại trên cọc B sang cọc C, lúc này lấy cọc A làm cọc trung gian.

Code sau được cài đặt trên IDE free pascal.

program ThapHaNoi;

procedure Chuyen(sodia:integer; CotNguon:char;CotDich:char;CotTrungGian: char);

begin

    if(sodia > 0) then

        begin

            Chuyen(sodia - 1,CotNguon,CotTrungGian, CotDich);

            writeln('Chuyen 1 dia tu cot ',CotNguon,'->', CotDich);

            Chuyen(sodia - 1,CotTrungGian, CotDich, CotNguon);

        end;

end;

begin

    Chuyen(3,'A','C','B');

    readln;

end.

Tham khảo:

http://en.wikipedia.org/wiki/Recursion

http://vi.wikipedia.org/wiki/Đệ_quy

http://vi.wikipedia.org/wiki/Tháp_Hà_Nội