BT-ĐỆ QUY-Lý thuyết đệ quy dể hiểu cho HS

quy

quy là pháp trình dùng trong tin trong đó có hàm chính nó.
Các bài toán hình khi quy:
        Bài toán tháp hà .
        Bài toán tính giai .
        Bài toán tính fibonaci.
Tuy nhiên khi quy chúng ta và gian trình.
Trong hàm quy chúng ta bao cũng có quy.
Bài toán tính giai .
Trong toán N! = 1.2.3…N, là tích N nguyên liên . là N giai .
Quy 0! = 1.
Chúng ta 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)! đó nhân N.
Chúng ta kê hàm tính giai sau, code sau trên free pascal.

program giaithua_dequy;
var
    n: longint;
(*trình con tính giai *)
function giaithua(m:longint):longint;
begin
(*
    writeln(`m=`,m);
    readln;
*)   
    if((m = 0) or (m = 1)) then giaithua := 1 (* quy *)
    else
        giaithua := giaithua(m - 1) * m;           (* hàm giai tính (m-1)! *)
end;

begin
    writeln(giaithua(5));
    readln;
end.

Bài toán dãy fibonaci: Dãy Fibonaci nghĩa sau:
F1 = 1, F2 = 1, Fn = Fn-1 + Fn-2.
các tiên dãy sau:
F3 = F2 + F1 = 1 + 1 = 2
F4 = F3 + F2 = 2 + 1 = 3
…..
ra ta trình nào?

code sau trình trên IDE free pascal.

program fibonaci;

function fibo(m: longint):longint;
begin
    (* 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à :
các đĩa kích khác nhau, có ở xuyên trên ba cái .
có ba cái A, B, C. Ban các đĩa trên A (), di các đĩa sang C (đích), B làm trung gian theo quy sau:
        di .
        đĩa trên đĩa có kích .
toán bài toán này theo quy sau:
        di N đĩa A sang C thì ta di N-1 đĩa sang trung gian B.
        ta di 1 đĩa còn trên A sang C.
        Sau đó N-1 đĩa còn trên B sang C, lúc này A làm trung gian.
Code sau cài 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.