A r t i c l e s
Navigation

Note: This Wiki is
outdated, personal views
may have changed.
L505 A.I. bot is dead
long live THX 1138

M a i n P a g e

D i r e c t o r y

Recursion versus Iterative Loops


program test; {$mode objfpc} {$H+}

{ recursion }
procedure testing1;
var i: longword;

  procedure loop;
  begin
    inc(i);
    if i = 80000 then exit;
    writeln('http://url.com/page?p=', i);
    loop; // tail..
  end;

begin
  i:= 0;
  loop;
end;

{ iterative alternative }
procedure testing2;
var i: longword;

  procedure loop;
  begin
    while i <> 80000 do
    begin
      inc(i);
      writeln('http://url.com/page?p=', i);
    end;
  end;

begin
  i:= 0;
  loop;
end;


begin
  testing2; // <-- fine
  testing1; // <-- not so fine, blow the stack
  readln;
end.

Maybe with the compiler optimizations it wouldn't blow the stack as easily. Recursion is interesting, but is really only recommended when you know the loop will get killed fairly soon. For example, if you are handling 301 redirects in HTTP, usually the 301 redirects will eventually lead to a web page after 2 or 3 redirects to the eventual 200 response.

In a large loop like above, using recursion can cause the stack to be blown up. In fact, sometimes I use recursion on purpose to stop people from doing silly things.. in my Fast Html Parser getrecurslinks demo I use a recursive loop like the above to prevent people from mining too many internet pages (since their stack will blow if they do). If they don't change the code, it will blow the stack.. so it stops them from extracting 300 million links on the internet.. of course I also put a 50 limit by doing this:

  procedure loop;
  begin
    if i = 50 then exit
    inc(i);
    loop;
  end;
If we skip the i = 50 check, then we can count on the stack blowing for our limitation. It's kind of a silly thing, to use recursion as a limitation.. i.e. blow the stack on purpose when some wise crack uses a misbehaved robot to steal 50 million links.. I just did it as a joke incase some clever numbskull deletes the if i = 50 limitation and thinks he is set to go ;-). One would have to change the recursive loop to an iterative loop in order to avoid blowing the stack, and/or turn on some compiler optimization that somehow cleverly avoids blowing the stack when tail recursion is known. Goto statements, anyone?

To see a real world recursive example which could have been done using a while loop instead of recursion (puzzle for you!), download my fast html parser demos and take a look into getrecurslinks.pas.

About
Note: This Wiki is outdated, personal views may have changed.

This wiki contains info on life, health, humans, nature, programming, database, fads, paradigms, poems, principles, theories.

Articles may contain statements which some may find helpful and encouraging, or even discouraging.

Beware, I believe in the Grand Justice system.
_ _ _