Tính giai thừa bằng đệ quy trong Pascal

Trong lập trình nói chung, một chương trình con (hàm, thủ tục) được gọi là đệ quy nếu trong quá trình thực hiện nó có phần phải gọi đến chính nó. So với việc sử dụng vòng lặp thì đệ quy có ưu điểm là tính trong sáng, nêu bật lên bản chất của vấn đề.

Bài viết hôm nay trình bày một ví dụ nhỏ về việc sử dụng đệ quy trong lập trình, đó là bài toán tính giai thừa bằng ngôn ngữ Pascal.

Ta đã biết giai thừa của một số tự nhiên n là $n!=n(n-1)(n-2)…3.2.1$, nếu $n=0$ thì $n!=1$. Dễ thấy

$$n!=n.(n-1)!$$

Như vậy giai thừa của một số $n$ sẽ bằng tích của chính nó với giai thừa của số liền trước, tức là việc tính giai thừa sẽ được lặp lại với $n$ lùi dần đến khi không thể lùi được nữa.

Trước tiên, ta xây dựng hàm đệ quy như sau:

function giaithua(n:Integer):LongInt;
begin
if n=0 then giaithua:=1 else giaithua:=n*giaithua(n-1);
end;

Hàm này phải được đặt trước phần begin của chương trình, đây là quy định của Pascal (phiền phức). Và đây là chương trình hoàn chỉnh!

program giai_thua;
uses Crt;
var n:Integer;

function giaithua(n:Integer):LongInt;
begin
if n=0 then giaithua:=1 else giaithua:=n*giaithua(n-1);
end;

begin
clrscr;
Write('Ban muon tinh giai thua cua bao nhieu:');
ReadLn(n);
WriteLn(n,'!=',giaithua(n));
ReadLn;
end.

Đợi rảnh rỗi, tôi viết chức năng này bằng PHP cho coi, ngắn và nhanh hơn nhiều.

Bình luận

Chia sẻ