Re: FAQ and string functions

[dennison@telepath.com (Ted Dennison)]

Ted Dennison <dennison@telepath.com> wrote in message news:<3D4BD17A.5000004@telepath.com>...
> There are some things you can do to help out though. For example, don't 
> declare anything locally that you don't need a separate copy of in each 
> recursive call. The same goes for passing parameters. This goes against 
> the usual rule of not using globals, but so be it. You can mitiagate the 
> maintainability pain by declaring the recursive routine inside of 
> another routine, which  contains the declarations for all the recursive 
> "globals". Also, try to code so that your algorithim is indeed 
> tail-recursive (and use the optimization).

Just to give an example, following is a rewrite of the algorithim I
gave in this post -
http://groups.google.com/groups?q=g:thl3084553553d&dq=&lr=&ie=UTF-8&selm=4519e058.0208020559.63f58040%40posting.google.com

earlier in this thread, but transformed a bit to not pass unneeded
data and to be (hopefully) tail-recursive. Again, this is uncompiled
and untested, so treat with a grain of salt.

-----------------------------------------------------------------------
-- Return a transformation of the Source string in such a way that all
-- (non-overlapping) occurances of From_Pattern are replaced by 
-- To_Pattern
function Transform (Source       : String; 
                    From_Pattern : String; 
                    To_Pattern   : String) return String is

   ------------------------------------------------------------------
   -- Return a string which is So_Far, with a transformation of Rest
   -- (based on the From_Pattern and To_Pattern) appended to it
   ------------------------------------------------------------------
   Transform_Rest (So_Far : String;
                   Rest   : String) return String is

      -- Find the location of the source pattern
      Pattern_Start : constant Natural := 
         Ada.Strings.Fixed.Index (Source  => Rest, 
                                  Pattern => From_Pattern);
   begin
      if Pattern_Start = 0 then
         return So_Far & Rest;
      else  
         -- Append the stuff before the From_Pattern, along with the
         -- To_Pattern, onto our So_Far transformed string, then have
         -- Transform_Rest transform the rest of it.
         return 
            Transform_Rest
              (So_Far => So_Far & 
                         Rest (Rest'First..Pattern_Start - 1) & 
                         To_Pattern,
               Rest   => Rest (Pattern_Start + From_Pattern'length ..
                               Rest'last)
              );
      end if;
   end Transform_Rest;
begin
   return Transform_Rest 
            (So_Far => "",
             Rest   => Source
            );
end Transform;

Note the following:

  1) We are no longer putting identical copies of the source and
target pattern on the stack with each recursive call. They are instead
global to Transform_Rest (but local to Transform). You'd be suprised
how much this can save you.

  2) We now accumulate the result string as we go, rather than tack it
onto the end of the return string.

  3) Because of 2, the recursive call no longer has any work to do
after it makes its own recursive call, other than return the result.
Therefore it is now tail-recursive.