Need expert help—fast? Use the Help Bell for personalized assistance getting answers to your important questions.

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.

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.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

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.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trialYour 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 ?

If 800 i must send comment to ex-ex with this.

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

However very thanx.

C++

From novice to tech pro — start learning today.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

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.