Solved

Removing Recursion

Posted on 1997-09-30
10
390 Views
Last Modified: 2008-03-06
Hi

When I need remove recursion from proc like :

Void P()
{
if (Expression(x))
  {
  A(x)
  P()
  B(x)
  }else C(x)
}

where x is global variables and A,B,C if functions on them.

Then I have this proc as result :

int N=0;
void P()
{
while (Expression(x))
  {
  A(X)
  N++
  }
C(x);while (N--!=0) B(x);
}

When I need remove recursion from proc like :

Void P()
{
if (Expression(x))
  {
  A(x)
  P()
  B(x)
  P()
  C(X)
  }else D(x)
}

Then I have this proc as result :

int N=1;
void P()
{
do
  { while (Expression(x)) { A(x); N*=2; }
    D(x);
    while ((N!=1) && (N%2)) { N=N/2;C(x); }
    if (N==1) goto koniec;
    N=N+1;
    B(x);
  } while (N!=1);
}

But i Have proc with 3 calls :

Void P()
{
if (Expression(x))
  {
  A(x)
  P()
  B(x)
  P()
  C(X)
  P()
  D(x)
  }else E(x)
}

I can't remove the Recursion. Mayby You can ?
I understand remove recursion in example 1 but not in example 2.

1).I give points with grade B in exchange for solution of example3.
2). I give points with grade A in exchange of description how Example2 was created.
3).I give all my points (at 30.iX i have 267pt) with grade A in exchange of Point1 and 2 of My Question.
0
Comment
Question by:mirek071497
10 Comments
 
LVL 84

Expert Comment

by:ozo
ID: 1170525
You didn't create example 2?
It looks to me like it's removing recursion by simulating a stack
In this case, a one bit wide stack stored in an int.
(BTW where is koniec?)
To remove recursion in 3, I think I'd prefer to simulate a stack with
a more natural structure, like an array.
It might also help to know why you want to remove recursion here.
It seems like the most natural way to do the above, but if there are other constraints,
it may help in designing an alternative to know what those constraints are.
0
 
LVL 3

Author Comment

by:mirek071497
ID: 1170526
Sorry koniec is end and it need be last in proc. I just try to see at this with you'r sugesstion. Thanx. If this help me i give you points.
0
 

Expert Comment

by:Bill_Gates
ID: 1170527
Don't remove recursion. At our company we insert recursion in all possible places and you know the results. It helps us to build hefty modules which never stop.
0
 
LVL 3

Author Comment

by:mirek071497
ID: 1170528
Bill_Gates.- If i will can grade with pt under 0 then you must give me answer.
0
 
LVL 4

Accepted Solution

by:
jos010697 earned 200 total points
ID: 1170529
The examples above mimic a stack. The second example is
quite sloppy, because the stack depth is limited to the
number of bits that can be stored in an int. Here's
an explanation of the first example:

rewrite your function P as follows:
 
   P --> A P B | C

which reads: P can 'expand' to 'A P B' or to a single C.
In the first case, 'A P B' can expand to 'A P B' again,
or to C. It doesn't take a rocket scientist to conclude
that P expands to A^n C B^n ('^n' denotes 'n times')

So, all what is needed here is a simple counter, counting
the number of times the first expansion is performed, hence
the solution:

   void P() {

      int count;

      for (count= 0; x; count++)
         A(x);

      C();

      while (count--)
         B(x);
   }

Now your second example, rewritten as follows:

   P --> A P B P C | D

As you can see, there are two positions where P can expand
again in the first expansion 'A P B P C'. Let' mimic a stack
here, using push() and pop() operations. Here goes:

   void P() {

      push(end);

      start;

      if (A(x) {

         push(lab1);
         goto start;

      lab1:

         B(x);

         push(lab2);
         goto start;

     lab2:
       
         C();
      }
      else
         D();

      goto pop();

   end:

   }

Now think of a stack as a number of bits. If the stack is
just a single bit 1 in the lowest position (i.e. the number 1),
it represents the label 'end' in the example above. Otherwise
a bit 0 represents 'lab1' and a bit 1 represents 'lab0'. Pushing
a 0 is performed by multiplying the 'stack' by 2, pushing a 1
is performed by adding a bit 1 in the lowest position.

As I wrote, there are not many bits in an int (32 most of the time), so only 16 recursion steps can be mimiced this way.

As a bonus ;-) here's the third example using push() and pop()
operations:

   void P() {

      push(end);
   
   start:
      if (x) {

         A(x);

         push(lab1);
         goto start;

      labl1:
         B();

         push(lab2);
         goto start;

      lab2:
         C();

         push(lab3);
         goto start;

      lab3:
         D();
      }
      else
         E();

      goto pop();

   end;
   }

kind regards,

Jos aka jos@and.nl

ps. BTW, nice question.
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 3

Author Comment

by:mirek071497
ID: 1170530
Hi jos. Big Thanx.
Your answer is not exactly what i need but this is very good start point. I can't now travers from you'r example to my ( in point2), because removing the gotos is very difficult in this.
Hovewer I can now remove recursion from all my procedures. You have very good idea ! Why i have not this before ?
0
 
LVL 3

Author Comment

by:mirek071497
ID: 1170531
Sorry ex-ex must made any mistake. I made grade, comment and increasion of points in the one submit. I see so this is now for 20pt. Do you receive 1000pt or 800 ?
If 800 i must send comment to ex-ex with this.
0
 
LVL 3

Author Comment

by:mirek071497
ID: 1170532
Hi. the points was not substracted from my account so this is next ex-ex error. I create now new question especcialy for you.
0
 
LVL 4

Expert Comment

by:jos010697
ID: 1170533
I don't care much about those points, take it easy; there's
no need to create a dummy question.

I you really want to eliminate those gotos too, hide them
in switch statements; something like this (second example);
the main idea is to control the flow with that explicit stack.
Here's a first attempt:

void P() {

        push(end);
        push(start);

        for(;;) {
                switch (pop()) {

                        case start:
                                if (A(x)) {
                                        push(lab1);
                                        push(start);
                                }
                                else
                                        D();
                                break;

                        case lab1:
                                B(x);
                                push(lab2);
                                push(start);
                                break;

                        case lab2:
                                C();
                                break;
                        case end:
                                return;
                }
        }
}

If you think that using a switch statement is cheating, you
can always translate the switch to a bunch of if ... else if
statements.

kind regards,

Jos aka jos@and.nl


0
 
LVL 3

Author Comment

by:mirek071497
ID: 1170534
Hi The code in my example 2 is better optimized, and i only sometimes programming in C, i need this for translate to Delphi. In Delphi i must change this to Case statement which is often very bad optimized.

However very thanx.
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

932 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now