Chương trình con

[hung06061995]

Em chẳng hiểu sự khác nhau giữa đệ qui và vòng lặp. Ai giải thích giùm em với. Nếu tốt thì cho em ví dụ chương trình chỉ có phép đệ qui giải được hay chương trình chỉ có phép vòng lặp giải được. Cảm ơn mọi người.

[thuonghcm]

V lặp là bạn chạy bộ vài vòng trên mặt đất, còn đệ qui là có thể bạn chạy trên chiếc xe buýt ...cũng.. đang chạy vậy ó

[QuyNam]

Thực chất của đệ qui là một vòng lặp. Đúng như bạn thuonghcm nói, nếu ví vòng lặp là xe đạp thì đệ qui là ôtô. Thuật toán được viết dưới dạng đệ qui thì gọn hơn, dễ hiểu hơn và tối ưu hơn.

VD : Tính lũy thừa : a^n

- Vòng lặp

var i:integer;
s:longint;
{Giả sử a và n nhập từ bàn phím}
begin
...
for i:=1 to n do s:=s*a;
...
end.

- Đệ qui

function exp(a,n:integer):longint;
begin
if n=0 then exp:=1 else exp:=a*exp(a,n-1)
end;

Và có không ít bài toán chỉ giải được bằng đệ qui

[bld]

đệ qui là "chia để trị"
đúng là chạy vòng vòng ...
nhưng qua cái ví dụ cũng thấy được sự khác nhau ...

[hung06061995]

Làm ơn giải thích rõ hơn giùm em tại sao thuật toán giải bằng đệ qui lại tối ưu hơn vòng lặp?

[bld]

đúng vậy đệ qui thì rất tốt :
cách viết ngắn gọn
không phải bao giờ cũng tối ưu hơn đâu !
rất khó để viết ra một chương trình đệ qui ,
những bài toán đệ qui đều có thể giải bằng vòng lặp ( khử đệ qui , cái này thì mình không rành lắm )
Đệ qui thì lại khá tốn không gian lưu trữ và thậm chí nó có thể lâu hơn vòng lặp
lấy một ví dụ đơn giản
để tính số fibonaci thứ 6
ta viết chương trình đệ quy

if i=1 or i=2 then F[i]:=1
else F[i]:=F[i-1]+F[[i-2];

sơ đồ tính toán

                   [f6]
                 /      \
              [f4]       [f5]
              / \        /  \ 
[f2],[f1]--[f3] [f2]   [f4] [f3]--[f2];[f1]
                       /  \
        [f2];[f1]---[f3] [f2]

rõ ràng f3 được tính đến 3 lần , f4 được tính 2 lần
trong khi đó , với vòng lặp :

a:=1
b:=1
for i:=1 to 6 do
 begin
  c:=a+b;
  a:=b;
  b:=c;
 end;
writeln(c);

thì rõ ràng chỉ cần 3 biến và các số fibo không bị tính lại nhiều lần
...

[hung06061995]

Mình vẫn không hiểu là tại sao nó lại tính tới 2 lần

[huysun]

Mình vẫn không hiểu là tại sao nó lại tính tới 2 lần

trong đệ qui, trong khi tính f[6] thì có câu lệnh tính f[6-2]=f[4], trong khi tình f[5] cũng có câu lệnh gọi f[5-1]=f[4].vì vậy f[4]phải tính lại 2 lần(máy tính nó "ngu" lắm, không phân biệt được cái nào có rồi, cái nào chưa đâu)

[hung06061995]

Ặc. VẪn khÔng hiỂu. ĐỪng ai nÓi mÌnh ngu nha.

[tank304]

Ai cũng có lúc hiểu hay chưa hiểu chứ bạn,cho mình hỏi vậy thì sử dụng đệ qui tối ưu hơn là dùng vòng lặp ở những điểm nào và cách sử dụng đệ qui đc ko?