Pascal - Sự tham khảo trước và sự ðệ qui

SỰ THAM KHẢO TRƯỚC VÀ SỰ ÐỆ QUI 13.3.1. Tham khảo trước (Forward reference): Bình thường khi trong chương trình chính có hai chương trình con A, B được khai báo kế tiếp nhau A trước, B sau, thì B gọi được A nhưng A không gọi được B. Khi đó để A gọi được B ta phải tiến hành khai báo phần đầu của B với từ khóa Forward trước khi khai báo B đầy đủ. Ví dụ 13.6: PROGRAM VIDU13_6; Procedure B; Forward ; { khai báo tham khảo B trước} Procedure A; Begin Writeln(‘ Chào chị ‘); B; End; Procedure B; Begin Writeln(‘ Chào anh ‘); End; BEGIN A; Readln; END. Chạy Chép tập tin nguồn Khi chương trình chạy sẽ in lên màn hình: Chào chị Chào anh Tất nhiên, nếu ta đưa khai báo đầy đủ B lên trước A thì không cần phải tham khảo trước. Song đặt giả thiết A gọi B rồi B lại gọi A thì nhất định phải tham khảo trước thôi. 13.3.2. Sự đệ qui (Recursion): Một thủ tục hay hàm có thể gọi chính nó, khi đó ta nói có sự đệ qui. Ví dụ 13.7: Tính S= k! bằng đệ qui. Ta viết : Muốn tính k! ta phải tính được (k-1)!, muốn tính (k-1)! lại phải tính (k- 2)!, ..., suy ra cuối cùng phải tính được 0!, nhưng vì 0!=1 nên qúa trình kết thúc. Chương trình sau nhập N, tính và in gía trị N!. Trong chương trình có xây dựng và sử dụng một hàm đệ quy tính k! : PROGRAM VIDU13_7; { Tính N! bằng đệ qui} Var N : Byte; Function Gt( k : Byte) : Real; { Hàm tính k! bằng đệ qui} Begin If k=0 then Gt:= 1 else Gt:= k* Gt(k-1); End; BEGIN Repeat Write(‘ Nhập N: ‘); Readln(N); Until N>0; Writeln( N, ‘ != ‘, Gt(N):0:0 ); Readln; END. Chạy Chép tập tin nguồn Khi nhập N=4, qúa trình gọi các hàm được diễn giải như sau: Gt(4) =4*Gt(3) =4*3*Gt(2) =4*3*2*Gt(1) =4*3*2*1*Gt(0) { vì k=0 nên Gt=1} =4*3*2*1* 1 =24. Ví dụ 13.8: Tính số hạng U(k) của dãy Fibonaci bằng đệ qui: U(0)=1, U(1)=1, U(k)=U(k-1) + U(k-2) với k>1. Ta viết: U(k) = 1 nếu k=0 hoặc k=1 = U(k-1) + U(k-2) nếu k>1. Công thức truy chứng trên là cơ sở để xây dựng hàm đệ qui tính U(k): để tính được một số hạng ta phải tính được hai số hạng đứng trước nó. Chương trình sau in ra số Fibonaci thứ N bằng cách gọi hàm đệ qui Fibo. PROGRAM VIDU13_8; { Tính số Fibonaci thứ N } Var N : Integer; Function Fibo( k : Integer) : Integer; { Hàm tính số Fibonaci thứ k bằng đệ qui} Begin If k=0 then Fibo:= 1 else if k=1 then Fibo:=1 else Fibo:=Fibo(k-1) + Fibo( k-2); End; BEGIN Write(‘ Nhập N: ‘); Readln(N); Writeln( ‘ Số Fibo thứ ‘, N, ‘ = ‘, Fibo(N) ); Readln; END. Chạy Chép tập tin nguồn Ghi chú: Việc sử dụng đệ qui đòi hỏi nhiều về bộ nhớ. Lời khuyên là nên tránh dùng đệ qui nếu có thể được.