Recursion elimination

[Lorenzo Villari]

I've tried to transform this into a not recursive version but without
luck...

#include <stdio.h>
void countdown(int p)
{
int x;

x = p - 1;

if(p != 0)
{
printf("%d\n", p);
countdown(x);
}
}
int main()
{
int i = 10;

countdown(i);

return 0;
}

[Steve Zimmerman]

Lorenzo Villari wrote:

I've tried to transform this into a not recursive version but without
luck...

#include <stdio.h>
void countdown(int p)
{
int x;

x = p - 1;

if(p != 0)
{
printf("%d\n", p);
countdown(x);
}
}
int main()
{
int i = 10;

countdown(i);

return 0;
}

#include <stdio.h>
void countdown(int upper_limit);

int main()
{
int i = 10;
countdown(i);

return 0;
}

void countdown(int upper_limit)
{
int i;

for (i = upper_limit; i > 0; i--)
printf("%d\n", i);
{

--Steve

[Jeff]

"Lorenzo Villari" <vl****@tiscali.it> wrote in message
news:lW**********************@twister2.libero.it.. .

I've tried to transform this into a not recursive version but without
luck...

#include <stdio.h>
void countdown(int p)
{
int x;

x = p - 1;

if(p != 0)
{
printf("%d\n", p);
countdown(x);
}
}
int main()
{
int i = 10;

countdown(i);

return 0;
}

Read the topic of "for-loop"

int main()
{
int i;

for(i=9; i!=0; i--)
{
printf("%d\n", i);
}

return 0;
}
--
Jeff

[Jeff]

"Jeff" <no*****@notexist.com> wrote in message
news:bj***********@news.hgc.com.hk...

"Lorenzo Villari" <vl****@tiscali.it> wrote in message
news:lW**********************@twister2.libero.it.. .

I've tried to transform this into a not recursive version but without
luck...

#include <stdio.h>
void countdown(int p)
{
int x;

x = p - 1;

if(p != 0)
{
printf("%d\n", p);
countdown(x);
}
}
int main()
{
int i = 10;

countdown(i);

return 0;
}
Read the topic of "for-loop"

int main()
{
int i;

for(i=9; i!=0; i--)
{
printf("%d\n", i);
}

Oh, it should be "for(i=10;i!=0;i--)"

Sorry.
return 0;
}
--
Jeff

[E. Robert Tisdale]

Lorenzo Villari wrote:

I've tried to transform this into a not recursive version
but without luck...
A *good* optimizing C compiler will do this for you.
cat recurse.c #include <stdio.h>

void countdown(int p) {
if(0 != p) {
printf("%d\n", p);
countdown(p - 1);
}
}

int main(int argc, char* argv[]) {
countdown(10);

return 0;
}
gcc -Wall -std=c99 -pedantic -O3 -S recurse.c
cat recurse.save

.file "recurse.c"
.section .rodata.str1.1,"aMS",@progbits,1
.LC0:
.string "%d\n"
.text
.align 2
.p2align 2,,3
.globl main
.type main,@function
main:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
andl $-16, %esp
subl $8, %esp
pushl $10
pushl $.LC0
call printf
movl $9, (%esp)
call countdown
addl $16, %esp
xorl %eax, %eax
leave
ret
.Lfe1:
.size main,.Lfe1-main
.align 2
.p2align 2,,3
.globl countdown
.type countdown,@function
countdown:
pushl %ebp
movl %esp, %ebp
pushl %ebx
pushl %eax
movl 8(%ebp), %ebx // p
.p2align 2,,3
.L9:
testl %ebx, %ebx // if (0 != p)
je .L7 // go to .L7
subl $8, %esp
pushl %ebx
pushl $.LC0
call printf // printf("%d\n", p)
decl %ebx // --p
addl $16, %esp
jmp .L9 // go to .L9
.L7:
movl -4(%ebp), %ebx
leave
ret
.Lfe2:
.size countdown,.Lfe2-countdown
.ident "GCC: (GNU) 3.2 20020903 \
(Red Hat Linux 8.0 3.2-7)"

[Vijay Kumar Zanvar]

#include <stdio.h>
void countdown2 ( int p )
{
for ( ; p; )
printf ( "%d\n", p-- );
}

int main()
{
int i = 10;

countdown2 (i);

return 0;
}

Lorenzo Villari wrote in message ...

I've tried to transform this into a not recursive version but without
luck...

#include <stdio.h>
void countdown(int p)
{
int x;

x = p - 1;

if(p != 0)
{
printf("%d\n", p);
countdown(x);
}
}
int main()
{
int i = 10;

countdown(i);

return 0;
}

-----------------------------------------------
Vijay Kumar R Zanvar

[Irrwahn Grausewitz]

"Vijay Kumar Zanvar" <vi*****@hotpop.com> wrote TOFU.
<SNIP>
Please don't TOFU (top-post, full quote).
--
Air is water with holes in it.

[Irrwahn Grausewitz]

"E. Robert Tisdale" <E.**************@jpl.nasa.gov> wrote in
<3F**************@jpl.nasa.gov>:

Lorenzo Villari wrote:

I've tried to transform this into a not recursive version
but without luck...

A *good* optimizing C compiler will do this for you.

#include <stdio.h>

void countdown(int p) {
if(0 != p) {
printf("%d\n", p);
countdown(p - 1);
}
}

int main(int argc, char* argv[]) {
countdown(10);

return 0;
}

<SNIP>
Assembler listing completely irrelevant!

--
Air is water with holes in it.

[LibraryUser]

Lorenzo Villari wrote:

I've tried to transform this into a not recursive version but
without luck...

#include <stdio.h>

void countdown(int p)
{
int x;

x = p - 1;
if(p != 0)
{
printf("%d\n", p);
countdown(x);
}
}

void countdown(int p)
{
while (p) {
printf("%d\n", p);
p = p - 1;
}
}

All of which will go off into the boondocks if p is supplied as a
negative value. Therefore a better test is (p > 0).

--
Replies should be to the newsgroup
Chuck Falconer, on vacation.

[Peter Ammon]

Lorenzo Villari wrote:

I've tried to transform this into a not recursive version but without
luck...

#include <stdio.h>
void countdown(int p)
{
int x;

x = p - 1;

if(p != 0)
{
printf("%d\n", p);
countdown(x);
}
}
int main()
{
int i = 10;

countdown(i);

return 0;
}

All recursive functions can be made iterative with an explicit stack.

Therefore, the right way to do this is with an explicit stack.

void countdown(int p) {
unsigned stackIndex = 0;
int stack[10];
#define PUSH(x) stack[stackIndex++]=(x)
#define POP() stack[--stackIndex]

PUSH(p);

beginning:
{
int p = POP();
int x;
x=p - 1;
if (p != 0)
{
printf("%d\n", p);
PUSH(x);
goto beginning;
}
}
}

-Peter

[Irrwahn Grausewitz]

Peter Ammon <pe*********@rocketmail.com> wrote in
<bj**********@news.apple.com>:

<OP's code snipped>

All recursive functions can be made iterative with an explicit stack. Err...
Therefore, the right way to do this is with an explicit stack. Ehm...

Somebody correct me please if I'm totally wrong [for me it's 2:00am],
but if you have to make excessive use of a stack, then this /is/
recursion after all...
void countdown(int p) {
unsigned stackIndex = 0;
int stack[10];
#define PUSH(x) stack[stackIndex++]=(x)
#define POP() stack[--stackIndex]

PUSH(p);

beginning:
{
int p = POP();
int x;
x=p - 1;
if (p != 0)
{
printf("%d\n", p);
PUSH(x);
goto beginning;
}
}
}

Yup, all you did is recursion the hard way: instead of using your
implementation's stack you built your own one and replaced the
recursive function call by a (Uck!) goto (Yuck!). At least you
could have replaced the (Yuck!) goto (Bleah!) with a while(1)/break
construct - but still this would be recursion, even if no recursive
function call takes place.

Remember: for iterative calculations you don't need a stack at all -
hence iteration will never overflow your stack, whereas recursion
might do - try to 'countdown( 20 );'.

The probably shortest possible iterative countdown function in C
would be:

void countdown( int p )
{
while ( p )
printf( "%d\n", p-- );
}
/* Merged from the suggestions of Mr. Zanvar and Mr. Falconer */

Irrwahn

--
My opinions are not those of my ex-employer.

[LibraryUser]

Irrwahn Grausewitz wrote:

.... snip ...
The probably shortest possible iterative countdown function in C
would be:

void countdown( int p )
{
while ( p )
printf( "%d\n", p-- );
}
/* Merged from the suggestions of Mr. Zanvar and Mr. Falconer */

I did not use the p-- construct because it would (possibly)
confuse the OP. You have not protected against calls with
negative p, BTW.

This conversion falls under the general class of end-around
recursion, where the recursive call is the last action of the
function. It can always be replaced by a loop after altering the
input parameters. Many compilers will automate this.

--
Replies should be to the newsgroup
Chuck Falconer, on vacation.

[Irrwahn Grausewitz]

LibraryUser <de**********@made.invalid> wrote in
<3F***************@made.invalid>:

Irrwahn Grausewitz wrote:
... snip ...

The probably shortest possible iterative countdown function in C
would be:

void countdown( int p )
{
while ( p )
printf( "%d\n", p-- );
}
/* Merged from the suggestions of Mr. Zanvar and Mr. Falconer */

I did not use the p-- construct because it would (possibly)
confuse the OP. You have not protected against calls with
negative p, BTW.

Definetely right. I'll make it:

void countdown( int p )
{
while ( p > 0 )
printf( "%d\n", p-- );
}

<SNIP>

--
No sig today.

[Peter Ammon]

Irrwahn Grausewitz wrote:

Peter Ammon <pe*********@rocketmail.com> wrote in
<bj**********@news.apple.com>:

<OP's code snipped>

All recursive functions can be made iterative with an explicit stack.
Err...

Therefore, the right way to do this is with an explicit stack.

Ehm...

Somebody correct me please if I'm totally wrong [for me it's 2:00am],
but if you have to make excessive use of a stack,

My use of a stack was very appropriate for what I intended to
accomplish, and in no way excessive.
then this /is/
recursion after all...

As a tongue out of cheek aside, I don't think most people would classify
this as recursion. I claim you can have a stack without recursion;
whats more, I claim you can have recursion without a stack. Look at
this code for adding two numbers:

unsigned foo(unsigned r3, unsigned r4) {
return r4 ? foo(++r3, --r4) : r3;
}

This is a bona-fide, guaranteed or your money back, indisputably
recursive function.

Here's gcc's assembly output for it:

L3:
cmpwi cr7,r4,0 /* compare r4 to 0 */
beqlr- cr7 /* return r3 if r4 is zero */
addi r3,r3,1 /* add one to r3 */
addi r4,r4,-1 /* subtract one from r4 */
b L3 /* go back to L3 */

Nowhere is any stack, including THE stack, touched, modified, or used at
all!

void countdown(int p) {
unsigned stackIndex = 0;
int stack[10];
#define PUSH(x) stack[stackIndex++]=(x)
#define POP() stack[--stackIndex]

PUSH(p);

beginning:
{
int p = POP();
int x;
x=p - 1;
if (p != 0)
{
printf("%d\n", p);
PUSH(x);
goto beginning;
}
}
}

Yup, all you did is recursion the hard way: instead of using your
implementation's stack you built your own one and replaced the
recursive function call by a (Uck!) goto (Yuck!).

Precisely, and hence, iteration!
At least you
could have replaced the (Yuck!) goto (Bleah!) with a while(1)/break
construct
But that wouldn't have captured the spirit of my solution.
- but still this would be recursion, even if no recursive
function call takes place.
Why?

Remember: for iterative calculations you don't need a stack at all -
hence iteration will never overflow your stack, whereas recursion
might do - try to 'countdown( 20 );'.
Ok, I tried countdown(20); in my code as above, and it worked fine. I
guess it must be iterative after all.

The probably shortest possible iterative countdown function in C
would be:

void countdown( int p )
{
while ( p )
printf( "%d\n", p-- );
}
/* Merged from the suggestions of Mr. Zanvar and Mr. Falconer */

countdown(-1);
puts("Houston, we have a problem...");

:>

-Peter

[Lorenzo Villari]

> Read the topic of "for-loop"

Ok but there's a way to "mechanically" eliminate recursion?
I mean something valid for all recursive functions,
expecially the ones with tail recursion...

For example... I've got a recursive function and I want to eliminate its
recursion but the code is too much and I can't post it...
automation (a formula) would be a solution...
(of course being a master of the language would be better...)

[Irrwahn Grausewitz]

Peter Ammon <pe*********@rocketmail.com> wrote in
<bj**********@news.apple.com>:
<SNIP>

As a tongue out of cheek aside, I don't think most people would classify
this as recursion. Hm, to be honest, looking at your code again I've noticed that I
misinterpreted it. All you do is alternating PUSH and POP, not
accumulating intermediate results on the stack (as I erroneously
thought from first glance). This way you need a maximum stack-size
of one. So, dealing with a stack in this case is IMHO nonsense at
all. Why not replace it with a temp-variable (a size 1 stack)?
Furthermore, why not eliminate even this, and end up with sth like
that:

void countdown( int p )
{
while( 1 )
{
int x;
x = p - 1;
if (p == 0)
break;
printf("%d\n", p);
p = x;
}
}

Looks familiar, yet still a bit more complex as necessary...
I claim you can have a stack without recursion; Nobody doubted.
whats more, I claim you can have recursion without a stack. <OT>
Well, you can have coffee without milk. :)
To get serious again: where will /real/ recursive code (not code
where recursion has been optimized away by the compiler, see below)
save the data (read:registers and values of automatic variables)
and the return address, if not in some place that at least /acts
like a stack/ ? [It may actually be some DNS in a test tube, but
who cares, as long as it resembles the funcionality of a lifo/stack
in some common platform architectures.]
</OT>
Look at this code for adding two numbers:

unsigned foo(unsigned r3, unsigned r4) {
return r4 ? foo(++r3, --r4) : r3;
}

This is a bona-fide, guaranteed or your money back, indisputably
recursive function. Agreed.
Here's gcc's assembly output for it:

L3:
cmpwi cr7,r4,0 /* compare r4 to 0 */
beqlr- cr7 /* return r3 if r4 is zero */
addi r3,r3,1 /* add one to r3 */
addi r4,r4,-1 /* subtract one from r4 */
b L3 /* go back to L3 */

Nowhere is any stack, including THE stack, touched, modified, or used at
all! Well, the (OT) compiler is free to produce anything, *as long as the
result matches the /intention/ of the source code*. If, for example,
you write a recursice faculty function, the (OT) compiler is free to
produce whatever code it likes, as long as it calculates the faculty!
This might very likely result in producing iterative code for a
recursive function, or what else modern /optimizing/ (OT) compilers
are capable of. I wonder what the result would look like, if you
compile foo() with (OT) code-optimization disabled...

<SNIP>

Yup, all you did is recursion the hard way: instead of using your
implementation's stack you built your own one and replaced the
recursive function call by a (Uck!) goto (Yuck!).

Precisely, and hence, iteration!

I have to agree, now that I've discovered the fault in my
interpretation.

At least you
could have replaced the (Yuck!) goto (Bleah!) with a while(1)/break
construct

But that wouldn't have captured the spirit of my solution.

Hm, what is the effective difference between

loop:
{
/* ... */;
}
goto loop;

and

while( 1 )
{
/* ... */;
}

respectively?

Or between (pseudocode):

loop:
/* ... */;
if ( <expr> )
goto loop;

and

while ( 1 )
{
/* ... */;
if ( !<expr> )
break;
}

and

do
{
/* ... */;
}
while ( <expr> );

respectively?

- but still this would be recursion, even if no recursive
function call takes place.

Why?

Q&A now obsolete, see above.

Remember: for iterative calculations you don't need a stack at all -
hence iteration will never overflow your stack, whereas recursion
might do - try to 'countdown( 20 );'.

Ok, I tried countdown(20); in my code as above, and it worked fine. I
guess it must be iterative after all.

Agreed, see above.

The probably shortest possible iterative countdown function in C
would be:

void countdown( int p )
{
while ( p )
printf( "%d\n", p-- );
}
/* Merged from the suggestions of Mr. Zanvar and Mr. Falconer */

Has been corrected already.
countdown(-1);
puts("Houston, we have a problem...");

And *EXACTLY* the same as with your code!!! :-P

Irrwahn
--
No sig today.

[E. Robert Tisdale]

Lorenzo Villari wrote:

Ok but there's a way to "mechanically" eliminate recursion?
I mean something valid for all recursive functions,
expecially the ones with tail recursion...

For example... I've got a recursive function and I want to eliminate its
recursion but the code is too much and I can't post it...
automation (a formula) would be a solution...
(of course being a master of the language would be better...)

Your C compiler should do this for you.

[Ben Pfaff]

"Lorenzo Villari" <vl****@tiscali.it> writes:

Ok but there's a way to "mechanically" eliminate recursion?
I mean something valid for all recursive functions,
expecially the ones with tail recursion...

For example... I've got a recursive function and I want to eliminate its
recursion but the code is too much and I can't post it...
automation (a formula) would be a solution...
(of course being a master of the language would be better...)

There's a mini-tutorial on eliminating recursion in my book on
binary search trees. You can read it at
http://adtinfo.org/libavl.html/Itera...-of-a-BST.html

It's not always the right thing to do to eliminate recursion.
However, there are several reasons to avoid recursion in C:

* Recursion is more difficult to understand in some
algorithms (but see below). An algorithm that can
naturally be expressed iteratively may not be as easy
to understand if expressed recursively.

* There is no portable way to tell how deep recursion can
go without causing trouble (how much `stack space' the
machine has), and there is no way to recover from
too-deep recursion (a `stack overflow').

* In C you can't do some nice things recursively. For
instance, if I'm traversing a binary tree, I probably
want to do it using a for loop:

tree t;
item *i;

for (i = first (t); i != NULL; i = next (i)) {
...do something with i...
}

But you can't write the traversal recursively if you
want to do this. Factoring the traversal into
iteration or forcing the use of a callback function are
the only two choices. The former is the lesser of the
two evils, since you only have to do it once and then
can use many times in traversals.

(Now, if C had built-in support for co-routines, we
could do this recursively anyhow. Most procedural
languages do not support co-routines; I hear that Icon
is an exception. It's really too bad, but I don't see
this changing soon.)

* Suppose that you need to pass some data to the
recursive process. You might want to keep a count of
the number of nodes visited, or a set of parameters
that determine what to do at each node, or anything
else. In order to do this, you have to pass some data
to every recursive call. This is a waste of time and
space, unless your compiler is much smarter than mine.
Alternatively, you can use global variables, but that's
hardly a preferable solution.

Now, if you were to use an iterative solution instead,
you could just have a single set of local variables,
and there is no need to pass anything recursively.
This saves the time and memory that would be used for
passing these things in the recursive calls.

* Aborting a recursive process in midstream is a pain.
Suppose that you're using a function to enumerate all
the items in a binary search tree, and you discover
halfway through that you don't need to look at any more
items. Alternatively, consider the problem of aborting
after a syntax error while parsing an expression via
recursive descent. Trying to abort the process
involves the cooperation of the currently executing
instance with all of the instances in which it is
nested. This is slow and sometimes nasty. Use of
setjmp() and longjmp() is an alternative, but, like
goto, these constructs are best avoided when practical.

Even worse, suppose, in the context of the binary
search tree example, that halfway through you discover
that you need to change directions, move *backward*. I
don't even want to think about how to do that
recursively. It's simply impractical.

* Avoiding recursive calls often avoids other kinds of
overhead, such as the system's unavoidable function
call overhead. On some systems this can be
significant, so a transformation from recursion to
iteration can improve both speed and space
requirements.

There are reasons to avoid iteration, too:

* Iteration is more difficult to understand in some
algorithms (but see above). An algorithm that can
naturally be expressed recursively may not be as easy
to understand if expressed iteratively. It can also be
difficult to convert a recursive algorithm into an
iterative algorithm, and verifying that the algorithms
are equivalent can also be difficult.

* Recursion allows you to allocate additional automatic
objects at each function call. The iterative
alternative is to repeatedly dynamically allocate or
resize memory blocks. On many platforms automatic
allocation is much faster, to the point that its speed
bonus outweighs the speed penalty and storage cost of
recursive calls. (But some platforms don't support
allocation of large amounts of automatic data, as
mentioned above; it's a trade-off.)

--
"We put [the best] Assembler programmers in a little glass case in the hallway
near the Exit sign. The sign on the case says, `In case of optimization
problem, break glass.' Meanwhile, the problem solvers are busy doing their
work in languages most appropriate to the job at hand." --Richard Riehle

[Morris Dovey]

Lorenzo Villari wrote:

Read the topic of "for-loop"

Ok but there's a way to "mechanically" eliminate recursion? I
mean something valid for all recursive functions, expecially
the ones with tail recursion...

Lorenzo...

No, not /all/ recursive functions can be implemented as
equivalent iterative functions.

I suspect that the subset of recursive functions whose exact
number of recursions can be calculated at time of invocation
/can/ be mechanically converted; and that the remainder can't -
but I have no proof to offer. 8^(
--
Morris Dovey
West Des Moines, Iowa USA
C links at http://www.iedu.com/c

[pete]

Irrwahn Grausewitz wrote:

LibraryUser <de**********@made.invalid> wrote in
<3F***************@made.invalid>:

Irrwahn Grausewitz wrote:
... snip ...

The probably shortest possible iterative countdown function in C
would be:

void countdown( int p )
{
while ( p )
printf( "%d\n", p-- );
}
/* Merged from the suggestions of Mr. Zanvar and Mr. Falconer */

I did not use the p-- construct because it would (possibly)
confuse the OP. You have not protected against calls with
negative p, BTW.

Definetely right. I'll make it:

void countdown( int p )
{
while ( p > 0 )
printf( "%d\n", p-- );
}

void countdown(unsigned p)
{
while ( p )
printf( "%u\n", p-- );
}

/*
** I like unsigned types for situations
** where negative values aren't allowed.
*/

--
pete

[E. Robert Tisdale]

Ben Pfaff wrote:

It's not always the right thing to do to eliminate recursion.

[snip]

For example, your optimizing C compiler will eliminate recursion
automatically for you if doing so actually results in
improved performance or efficiency.

If you have a recursive formula,
it is probably best to code it as a recurse function
and let your optimizing C compiler "flatten" it automatically.

[Peter Nilsson]

Irrwahn Grausewitz <ir*****@freenet.de> wrote in message news:<i0********************************@4ax.com>. ..

Peter Ammon <pe*********@rocketmail.com> wrote in
<bj**********@news.apple.com>:

<OP's code snipped>

All recursive functions can be made iterative with an explicit stack. Err...

Therefore, the right way to do this is with an explicit stack.

Ehm...

Somebody correct me please if I'm totally wrong [for me it's 2:00am],
but if you have to make excessive use of a stack, then this /is/
recursion after all...

I'd say: if you're using a stack to explicitly mimic the implicit
stack used by recursion, then you're just mimicing recursion.
[Handwaving with terms like 'excessive' is not constructive.]

The debate is really a theoretical one IMO, and best suited to a group
dealing with computation theory where the definitions of what is what
are a tad more rigorous than individual's notions.

void countdown(int p) {
unsigned stackIndex = 0;
int stack[10];
#define PUSH(x) stack[stackIndex++]=(x)
#define POP() stack[--stackIndex]

PUSH(p);

beginning:
{
int p = POP();
int x;
x=p - 1;
if (p != 0)
{
printf("%d\n", p);
PUSH(x);
goto beginning;
}
}
}

Yup, all you did is recursion the hard way...

Agreed. I'd only do it if I *had* to.
Remember: for iterative calculations you don't need a stack at all -
hence iteration will never overflow your stack,
There is no standard guarantee that calling even a single user defined
function (not necessarily a recursive one) won't blow an
implementation's notional stack.

How much recursion is allowed by an implementation is a QoI issue.
whereas recursion
might do - try to 'countdown( 20 );'.

I wouldn't try to quantify the argument as you'd have to play straw
man and keep increasing the number whilst the replies are 'it still
works'.

Peter Ammon's reply that a compiler might be capable of optimising out
the explicit stack is an ironic one since that same compiler stands a
good chance of turning the recursive solution into an internal
iterative one anyway!

Fundamentally, recursion, iteration, and programming languages in
general are just attempts to best express algorithms from a human
perspective in a manner that is convertable to machine executable
form.

With compiler technology being what it is today, programmers should
always prefer the most succint and appropriate (even 'elegent') form
of expression to codify their algorithms, then let the compiler do the
leg work. Of course the choice of style is a subjective one and
sometimes practical issues do get in the way of a good solution. :-)

--
Peter

[James Hu]

"Lorenzo Villari" <vl****@tiscali.it> wrote in message news:<lW**********************@twister2.libero.it> ...

I've tried to transform this into a not recursive version but without
luck...

#include <stdio.h>

void countdown(int p)
{
int x;

x = p - 1;

if(p != 0)
{
printf("%d\n", p);
countdown(x);
}
}

A tail recursive function can be mechanically converted to an
iterative function. First, let us re-write countdown to be
tail recursive:

void countdown(int p)
{
int x;

if (p == 0) return;
x = p-1;
printf("%d\n", p);
countdown(x);
}

Because the function is tail recursive, the function argument
can be reused (since it is not needed after the return of the
recursive call), and then we turn the call into a goto:

void countdown(int p)
{
int x;

loop:
if (p == 0) return;
x = p-1;
printf("%d\n", p);
p = x;
goto loop;
}

The if/goto construct can be easily converted to a while loop:

void countdown(int p)
{
int x;

while (!(p == 0)) {
x = p-1;
printf("%d\n", p);
p = x;
}
}
-- James

[Ben Pfaff]

ai***@acay.com.au (Peter Nilsson) writes:

I'd say: if you're using a stack to explicitly mimic the implicit
stack used by recursion, then you're just mimicing recursion.

Mimicking recursion still has real advantages over real recursion
in some contexts. Earlier I posted my list of points for and
against recursion in C. The following of those points still
apply to iteration that mimics recursion. None of these say
"recursion is (faster/slower) than iteration"; they are all
related to convenience and practicality (well, the third point
has a little to do with efficiency but a lot more to do with
convenience):

* There is no portable way to tell how deep recursion can
go without causing trouble (how much `stack space' the
machine has), and there is no way to recover from
too-deep recursion (a `stack overflow').

* In C you can't do some nice things recursively. For
instance, if I'm traversing a binary tree, I probably
want to do it using a for loop:

tree t;
item *i;

for (i = first (t); i != NULL; i = next (i)) {
...do something with i...
}

But you can't write the traversal recursively if you
want to do this. Factoring the traversal into
iteration or forcing the use of a callback function are
the only two choices. The former is the lesser of the
two evils, since you only have to do it once and then
can use many times in traversals.

* Suppose that you need to pass some data to the
recursive process. You might want to keep a count of
the number of nodes visited, or a set of parameters
that determine what to do at each node, or anything
else. In order to do this, you have to pass some data
to every recursive call. This is a waste of time and
space, unless your compiler is much smarter than mine.
Alternatively, you can use global variables, but that's
hardly a preferable solution.

Now, if you were to use an iterative solution instead,
you could just have a single set of local variables,
and there is no need to pass anything recursively.
This saves the time and memory that would be used for
passing these things in the recursive calls.

* Aborting a recursive process in midstream is a pain.
Suppose that you're using a function to enumerate all
the items in a binary search tree, and you discover
halfway through that you don't need to look at any more
items. Alternatively, consider the problem of aborting
after a syntax error while parsing an expression via
recursive descent. Trying to abort the process
involves the cooperation of the currently executing
instance with all of the instances in which it is
nested. This is slow and sometimes nasty. Use of
setjmp() and longjmp() is an alternative, but, like
goto, these constructs are best avoided when practical.

Even worse, suppose, in the context of the binary
search tree example, that halfway through you discover
that you need to change directions, move *backward*. I
don't even want to think about how to do that
recursively. It's simply impractical.

In short, I don't think that mimicking recursion should be
derided just because it's imitation; rather, it should be done
when it's the right thing to do, and avoided when it's done for
gratuitous reasons.
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

[Peter Ammon]

Irrwahn Grausewitz wrote:

Peter Ammon <pe*********@rocketmail.com> wrote in
<bj**********@news.apple.com>:
<SNIP>

As a tongue out of cheek aside, I don't think most people would classify
this as recursion.
Hm, to be honest, looking at your code again I've noticed that I
misinterpreted it. All you do is alternating PUSH and POP, not
accumulating intermediate results on the stack (as I erroneously
thought from first glance). This way you need a maximum stack-size
of one. So, dealing with a stack in this case is IMHO nonsense at
all. Why not replace it with a temp-variable (a size 1 stack)?

It was left as an exercise to the reader.
Furthermore, why not eliminate even this,
See above. :)
and end up with sth like
that:

void countdown( int p )
{
while( 1 )
{
int x;
x = p - 1;
if (p == 0)
break;
printf("%d\n", p);
p = x;
}
}

Looks familiar, yet still a bit more complex as necessary...

I claim you can have a stack without recursion;
Nobody doubted.

whats more, I claim you can have recursion without a stack.

<OT>
Well, you can have coffee without milk. :)
To get serious again: where will /real/ recursive code (not code
where recursion has been optimized away by the compiler, see below)
save the data (read:registers and values of automatic variables)
and the return address, if not in some place that at least /acts
like a stack/ ? [It may actually be some DNS in a test tube, but
who cares, as long as it resembles the funcionality of a lifo/stack
in some common platform architectures.]
</OT>

Indeed, to implement non tail recursive functions in general, you need
something that acts like a stack.

[...]
Well, the (OT) compiler is free to produce anything, *as long as the
result matches the /intention/ of the source code*. If, for example,
you write a recursice faculty function, the (OT) compiler is free to
produce whatever code it likes, as long as it calculates the faculty!
This might very likely result in producing iterative code for a
recursive function, or what else modern /optimizing/ (OT) compilers
are capable of. I wonder what the result would look like, if you
compile foo() with (OT) code-optimization disabled...

[OT]
Funny you should ask. :) Without optimizations, my compiler will
allocate space on the stack even if it is never used.
[/OT]
<SNIP>

Yup, all you did is recursion the hard way: instead of using your
implementation's stack you built your own one and replaced the
recursive function call by a (Uck!) goto (Yuck!).
Precisely, and hence, iteration!

I have to agree, now that I've discovered the fault in my
interpretation.

At least you
could have replaced the (Yuck!) goto (Bleah!) with a while(1)/break
construct

But that wouldn't have captured the spirit of my solution.

Hm, what is the effective difference between

loop:
{
/* ... */;
}
goto loop;

and

while( 1 )
{
/* ... */;
}

respectively?

Or between (pseudocode):

loop:
/* ... */;
if ( <expr> )
goto loop;

and

while ( 1 )
{
/* ... */;
if ( !<expr> )
break;
}

and

do
{
/* ... */;
}
while ( <expr> );

respectively?

Ok, you called me out. My response had two purposes:

1) To be a jerk and give a technically correct but practically useless
solution.
2) To illustrate the statement I made at the beginning: that all
recursive functions can be made iterative (in the sense of the function
not calling itself) via an explicit stack, and furthermore, that this
can be done in a very mechanical, algorithmic way. I used goto because
it's the sort of thing you would get using an algorithm rather than
understanding of the particular problem and creativity (like you might
get with a code generator).

And what luck! I notice that the OP is asking for just such a mechnical
way, so in case he's reading:

[OT?]

Yes, every recursive function can be replaced with an iterative
function; this is a mathematical theorem that says that every computable
function can be implemented with while loops. (A computable function is
something that a Turing machine can do.) Yes, there is a mechanical
algorithm to replace recursion with iteration using an explicit stack.
If you were to apply such an algorithm to the code you gave at the
beginning, you might come up with something very much like the code I
gave you as a solution. I hope you can see how to apply it in general.

[/OT?]

[...]

countdown(-1);
puts("Houston, we have a problem...");

And *EXACTLY* the same as with your code!!! :-P

/me looks stricken

-Peter

[Peter Ammon]

Ben Pfaff wrote:

[...]

* Suppose that you need to pass some data to the
recursive process. You might want to keep a count of
the number of nodes visited, or a set of parameters
that determine what to do at each node, or anything
else. In order to do this, you have to pass some data
to every recursive call. This is a waste of time and
space, unless your compiler is much smarter than mine.
Alternatively, you can use global variables, but that's
hardly a preferable solution.

Now, if you were to use an iterative solution instead,
you could just have a single set of local variables,
and there is no need to pass anything recursively.
This saves the time and memory that would be used for
passing these things in the recursive calls.

This is one reason why I'd really like to have lexically scoped
("nested") functions in C. You could use a local variable in the
"outer" function that the recursive inner function could access, without
polluting the global namespace or wasting memory.

I understand that this is difficult for compiler writers to implement,
however.

[...]

-Peter

[LibraryUser]

Morris Dovey wrote:

Lorenzo Villari wrote:

Ok but there's a way to "mechanically" eliminate recursion? I
mean something valid for all recursive functions, expecially
the ones with tail recursion...
No, not /all/ recursive functions can be implemented as
equivalent iterative functions.

On the contrary, ALL recursive functions can be automatically
converted to iteration with the aid of an auxiliary stack. I
believe Knuth, Sedgewick, and Wirth at least cover the subject
adequately.
I suspect that the subset of recursive functions whose exact
number of recursions can be calculated at time of invocation
/can/ be mechanically converted; and that the remainder can't -
but I have no proof to offer. 8^(

This 'pre-calculation' is another matter, and obviously depends
on the actual data structure present, which in turn is
independant of the actual recursion. However, one advantage of
the conversion to iteration is that the auxiliary stack can
easily have tests for full and empty (besides push and pop
operations) which enable easy detection of failure conditions,
and may even allow automatic stack expansion.

--
Replies should be to the newsgroup
Chuck Falconer, on vacation.

[LibraryUser]

pete wrote:

Irrwahn Grausewitz wrote:

LibraryUser <de**********@made.invalid> wrote in

Irrwahn Grausewitz wrote:

... snip ...
>
> The probably shortest possible iterative countdown function
> in C would be:
>
> void countdown( int p )
> {
> while ( p )
> printf( "%d\n", p-- );
> }
> /* Merged from the suggestions of Mr. Zanvar and Mr. Falconer */

I did not use the p-- construct because it would (possibly)
confuse the OP. You have not protected against calls with
negative p, BTW.

Definetely right. I'll make it:

void countdown( int p )
{
while ( p > 0 )
printf( "%d\n", p-- );
}

void countdown(unsigned p)
{
while ( p )
printf( "%u\n", p-- );
}

/*
** I like unsigned types for situations
** where negative values aren't allowed.
*/

However that doesn't protect against caller misuse, or give the
(rare) advantage of a crash at integer overflow. Of course the
action taken depends on the real usage, and has no absolutely
correct solution.

--
Replies should be to the newsgroup
Chuck Falconer, on vacation.

[LibraryUser]

Peter Ammon wrote:

Ben Pfaff wrote:

[...]

* Suppose that you need to pass some data to the
recursive process. You might want to keep a count of
the number of nodes visited, or a set of parameters
that determine what to do at each node, or anything
else. In order to do this, you have to pass some data
to every recursive call. This is a waste of time and
space, unless your compiler is much smarter than mine.
Alternatively, you can use global variables, but that's
hardly a preferable solution.

Now, if you were to use an iterative solution instead,
you could just have a single set of local variables,
and there is no need to pass anything recursively.
This saves the time and memory that would be used for
passing these things in the recursive calls.

This is one reason why I'd really like to have lexically scoped
("nested") functions in C. You could use a local variable in
the "outer" function that the recursive inner function could
access, without polluting the global namespace or wasting memory.

I understand that this is difficult for compiler writers to
implement, however.

No it isn't (difficult). It just isn't part of standard C.
Pascal and Ada routinely implement it, and it is an available
(non-portable) extension under GCC.

--
Replies should be to the newsgroup
Chuck Falconer, on vacation.

[LibraryUser]

Morris Dovey wrote:

Lorenzo Villari wrote:

Ok but there's a way to "mechanically" eliminate recursion? I
mean something valid for all recursive functions, expecially
the ones with tail recursion...
No, not /all/ recursive functions can be implemented as
equivalent iterative functions.

On the contrary, ALL recursive functions can be automatically
converted to iteration with the aid of an auxiliary stack. I
believe Knuth, Sedgewick, and Wirth at least cover the subject
adequately.
I suspect that the subset of recursive functions whose exact
number of recursions can be calculated at time of invocation
/can/ be mechanically converted; and that the remainder can't -
but I have no proof to offer. 8^(

This 'pre-calculation' is another matter, and obviously depends
on the actual data structure present, which in turn is
independant of the actual recursion. However, one advantage of
the conversion to iteration is that the auxiliary stack can
easily have tests for full and empty (besides push and pop
operations) which enable easy detection of failure conditions,
and may even allow automatic stack expansion.

--
Replies should be to the newsgroup
Chuck Falconer, on vacation.

[LibraryUser]

pete wrote:

Irrwahn Grausewitz wrote:

LibraryUser <de**********@made.invalid> wrote in

Irrwahn Grausewitz wrote:

... snip ...
>
> The probably shortest possible iterative countdown function
> in C would be:
>
> void countdown( int p )
> {
> while ( p )
> printf( "%d\n", p-- );
> }
> /* Merged from the suggestions of Mr. Zanvar and Mr. Falconer */

I did not use the p-- construct because it would (possibly)
confuse the OP. You have not protected against calls with
negative p, BTW.

Definetely right. I'll make it:

void countdown( int p )
{
while ( p > 0 )
printf( "%d\n", p-- );
}

void countdown(unsigned p)
{
while ( p )
printf( "%u\n", p-- );
}

/*
** I like unsigned types for situations
** where negative values aren't allowed.
*/

However that doesn't protect against caller misuse, or give the
(rare) advantage of a crash at integer overflow. Of course the
action taken depends on the real usage, and has no absolutely
correct solution.

--
Replies should be to the newsgroup
Chuck Falconer, on vacation.

[LibraryUser]

Peter Ammon wrote:

Ben Pfaff wrote:

[...]

* Suppose that you need to pass some data to the
recursive process. You might want to keep a count of
the number of nodes visited, or a set of parameters
that determine what to do at each node, or anything
else. In order to do this, you have to pass some data
to every recursive call. This is a waste of time and
space, unless your compiler is much smarter than mine.
Alternatively, you can use global variables, but that's
hardly a preferable solution.

Now, if you were to use an iterative solution instead,
you could just have a single set of local variables,
and there is no need to pass anything recursively.
This saves the time and memory that would be used for
passing these things in the recursive calls.

This is one reason why I'd really like to have lexically scoped
("nested") functions in C. You could use a local variable in
the "outer" function that the recursive inner function could
access, without polluting the global namespace or wasting memory.

I understand that this is difficult for compiler writers to
implement, however.

No it isn't (difficult). It just isn't part of standard C.
Pascal and Ada routinely implement it, and it is an available
(non-portable) extension under GCC.

--
Replies should be to the newsgroup
Chuck Falconer, on vacation.

[Morris Dovey]

LibraryUser wrote:

Morris Dovey wrote:

Lorenzo Villari wrote:

Ok but there's a way to "mechanically" eliminate recursion? I
mean something valid for all recursive functions, expecially
the ones with tail recursion...

No, not /all/ recursive functions can be implemented as
equivalent iterative functions.

On the contrary, ALL recursive functions can be automatically
converted to iteration with the aid of an auxiliary stack. I
believe Knuth, Sedgewick, and Wirth at least cover the subject
adequately.

I suspect that the subset of recursive functions whose exact
number of recursions can be calculated at time of invocation
/can/ be mechanically converted; and that the remainder can't -
but I have no proof to offer. 8^(

This 'pre-calculation' is another matter, and obviously depends
on the actual data structure present, which in turn is
independant of the actual recursion. However, one advantage of
the conversion to iteration is that the auxiliary stack can
easily have tests for full and empty (besides push and pop
operations) which enable easy detection of failure conditions,
and may even allow automatic stack expansion.

Ok. My favorite (old) example problem is the mechanical (which I
take to mean "not as a single special case") conversion of
http://www.iedu.com/mrd/c/mgets.c to an equivalent iterative
solution. Note that the primary constraint on the existing
recursive solution is that no dynamic allocation take place until
the exact size of the input has been determined. That same
constraint must apply to any iterative solution in order for the
program to be "equivalent".

I'm not questioning the plausibility of an iterative solution -
I've already done that myself. What I /am/ questioning is the
availability of an algorithm which will recognize the constraints
built into recursive logic and correctly produce an equivalent
iterative logic flow that satisfies those same constraints.

I can't claim to have read works of the authors you listed (and
can't even remember the titles of those I have read); but I'm
sure that in the course of my own reading I haven't seen either
the algorithm or the proof that an equivalent conversion can (or
cannot) be produced.

Would you be kind enough to pinpoint the specific reference(s)
for me? Please don't waste your vacation time on this if you
don't have the info at your fingertips - wait until you're back
home and have time - but I /am/ interested.

--
Morris Dovey
West Des Moines, Iowa USA
C links at http://www.iedu.com/c

[Joona I Palaste]

LibraryUser <de**********@made.invalid> scribbled the following:

Peter Ammon wrote:

Ben Pfaff wrote:

[...]

>
> * Suppose that you need to pass some data to the
> recursive process. You might want to keep a count of
> the number of nodes visited, or a set of parameters
> that determine what to do at each node, or anything
> else. In order to do this, you have to pass some data
> to every recursive call. This is a waste of time and
> space, unless your compiler is much smarter than mine.
> Alternatively, you can use global variables, but that's
> hardly a preferable solution.
>
> Now, if you were to use an iterative solution instead,
> you could just have a single set of local variables,
> and there is no need to pass anything recursively.
> This saves the time and memory that would be used for
> passing these things in the recursive calls.
This is one reason why I'd really like to have lexically scoped
("nested") functions in C. You could use a local variable in
the "outer" function that the recursive inner function could
access, without polluting the global namespace or wasting memory.

I understand that this is difficult for compiler writers to
implement, however.

No it isn't (difficult). It just isn't part of standard C.
Pascal and Ada routinely implement it, and it is an available
(non-portable) extension under GCC.

It's hard to even specify how nested functions should work in C. This is
because of function pointers. Suppose you got hold of a function pointer
pointing to a nested inner function, outside of the enclosing outer
function. This nested inner function would then access variables defined
in the outer function - what then?

--
/-- Joona Palaste (pa*****@cc.helsinki.fi) ---------------------------\
| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste W++ B OP+ |
\----------------------------------------- Finland rules! ------------/
"I said 'play as you've never played before', not 'play as IF you've never
played before'!"
- Andy Capp

[Lorenzo Villari]

Ok. My favorite (old) example problem is the mechanical (which I
take to mean "not as a single special case") conversion of
http://www.iedu.com/mrd/c/mgets.c to an equivalent iterative
solution. Note that the primary constraint on the existing

I was interested in your example but I get

404 - Page not found
Unable to retrieve /mrd/c/mgets.c.

[LibraryUser]

Joona I Palaste wrote:

LibraryUser <de**********@made.invalid> scribbled the following:

[...]

No it isn't (difficult). It just isn't part of standard C.
Pascal and Ada routinely implement it, and it is an available
(non-portable) extension under GCC.

It's hard to even specify how nested functions should work in C.
This is because of function pointers. Suppose you got hold of a
function pointer pointing to a nested inner function, outside of
the enclosing outer function. This nested inner function would
then access variables defined in the outer function - what then?

In Pascal, at least, this is handled in a similar manner to C
handling of pointers to local variables - they are illegal once
the enclosing scope is no longer active. Of course Pascal
doesn't have pointers to functions, just references to them, but
the principle is the same.

--
Replies should be to the newsgroup
Chuck Falconer, on vacation.

[Joona I Palaste]

LibraryUser <de**********@made.invalid> scribbled the following:

Joona I Palaste wrote:

LibraryUser <de**********@made.invalid> scribbled the following:

>>
>> [...]

> No it isn't (difficult). It just isn't part of standard C.
> Pascal and Ada routinely implement it, and it is an available
> (non-portable) extension under GCC.

It's hard to even specify how nested functions should work in C.
This is because of function pointers. Suppose you got hold of a
function pointer pointing to a nested inner function, outside of
the enclosing outer function. This nested inner function would
then access variables defined in the outer function - what then?

In Pascal, at least, this is handled in a similar manner to C
handling of pointers to local variables - they are illegal once
the enclosing scope is no longer active. Of course Pascal
doesn't have pointers to functions, just references to them, but
the principle is the same.

In C, indirecting through a pointer which is pointing at something not
in scope any more is undefined behaviour. What is it in Pascal? A run-
time error?

--
/-- Joona Palaste (pa*****@cc.helsinki.fi) ---------------------------\
| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste W++ B OP+ |
\----------------------------------------- Finland rules! ------------/
"We sorcerers don't like to eat our words, so to say."
- Sparrowhawk

[LibraryUser]

Joona I Palaste wrote:

LibraryUser <de**********@made.invalid> scribbled the following:

Joona I Palaste wrote:

LibraryUser <de**********@made.invalid> scribbled the following:
>>
>> [...]

> No it isn't (difficult). It just isn't part of standard C.
> Pascal and Ada routinely implement it, and it is an available
> (non-portable) extension under GCC.

It's hard to even specify how nested functions should work in C.
This is because of function pointers. Suppose you got hold of a
function pointer pointing to a nested inner function, outside of
the enclosing outer function. This nested inner function would
then access variables defined in the outer function - what then?

In Pascal, at least, this is handled in a similar manner to C
handling of pointers to local variables - they are illegal once
the enclosing scope is no longer active. Of course Pascal
doesn't have pointers to functions, just references to them, but
the principle is the same.

In C, indirecting through a pointer which is pointing at something
not in scope any more is undefined behaviour. What is it in Pascal?
A run-time error?

Pascal attempts to diagnose errors at compile time. Since it
doesn't have function pointers, but only the ability to pass
functions to other functions, that function has to be in scope at
the call. Thus the problem never arises.

Some people consider this sort of attitude restrictive; I
consider it extremely helpful. I believe extended (ISO10206)
Pascal has further provisions, but am not certain. For example,
limiting function pointers to global procedures would suffice.
Since all C functions/procedures are global, this automatically
applies to C. (for a reasonable meaning of global).

--
Replies should be to the newsgroup
Chuck Falconer, on vacation.

[Bill Reed]

On Sun, 07 Sep 2003 11:29:18 GMT, "Lorenzo Villari"
<vl****@tiscali.it> wrote:

Ok. My favorite (old) example problem is the mechanical (which I
take to mean "not as a single special case") conversion of
http://www.iedu.com/mrd/c/mgets.c to an equivalent iterative
solution. Note that the primary constraint on the existing

I was interested in your example but I get

404 - Page not found
Unable to retrieve /mrd/c/mgets.c.

That may have been a typo. I found getsm.c at
http://www.iedu.com/mrd/c

Bill

[Kevin Easton]

Joona I Palaste <pa*****@cc.helsinki.fi> wrote:
[...nested functions in C...]

It's hard to even specify how nested functions should work in C. This is
because of function pointers. Suppose you got hold of a function pointer
pointing to a nested inner function, outside of the enclosing outer
function. This nested inner function would then access variables defined
in the outer function - what then?

I believe under the traditional model of nested functions, the function
pointer would only be valid as long as the particular function
invocation (containing the nested function) that created it was still
executing - so it can only be passed down the call graph and not up.
Additionally, any references it makes to variables of the enclosing
function refer to the instance of those variables corresponding to the
instance of the containing function that created the function pointer.

- Kevin.

[Joona I Palaste]

LibraryUser <de**********@made.invalid> scribbled the following:

Joona I Palaste wrote:

LibraryUser <de**********@made.invalid> scribbled the following:

> Joona I Palaste wrote:
>> LibraryUser <de**********@made.invalid> scribbled the following:
>> >>
>> >> [...]
>>
>> > No it isn't (difficult). It just isn't part of standard C.
>> > Pascal and Ada routinely implement it, and it is an available
>> > (non-portable) extension under GCC.
>>
>> It's hard to even specify how nested functions should work in C.
>> This is because of function pointers. Suppose you got hold of a
>> function pointer pointing to a nested inner function, outside of
>> the enclosing outer function. This nested inner function would
>> then access variables defined in the outer function - what then?

> In Pascal, at least, this is handled in a similar manner to C
> handling of pointers to local variables - they are illegal once
> the enclosing scope is no longer active. Of course Pascal
> doesn't have pointers to functions, just references to them, but
> the principle is the same.

In C, indirecting through a pointer which is pointing at something
not in scope any more is undefined behaviour. What is it in Pascal?
A run-time error?

Pascal attempts to diagnose errors at compile time. Since it
doesn't have function pointers, but only the ability to pass
functions to other functions, that function has to be in scope at
the call. Thus the problem never arises. Some people consider this sort of attitude restrictive; I
consider it extremely helpful. I believe extended (ISO10206)
Pascal has further provisions, but am not certain. For example,
limiting function pointers to global procedures would suffice.
Since all C functions/procedures are global, this automatically
applies to C. (for a reasonable meaning of global).

A-aga... doesn't Pascal have pointers to scalars (integers etc.) just
like C does? What happens if a Pascal function returns a pointer
pointing to an integer outside of scope, and then the calling procedure
or function indirects through that pointer?

--
/-- Joona Palaste (pa*****@cc.helsinki.fi) ---------------------------\
| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste W++ B OP+ |
\----------------------------------------- Finland rules! ------------/
"You have moved your mouse, for these changes to take effect you must shut down
and restart your computer. Do you want to restart your computer now?"
- Karri Kalpio

[Morris Dovey]

Bill Reed wrote:

On Sun, 07 Sep 2003 11:29:18 GMT, "Lorenzo Villari"
<vl****@tiscali.it> wrote:

Ok. My favorite (old) example problem is the mechanical
(which I take to mean "not as a single special case")
conversion of http://www.iedu.com/mrd/c/mgets.c to an
equivalent iterative solution. Note that the primary
constraint on the existing

I was interested in your example but I get

404 - Page not found Unable to retrieve /mrd/c/mgets.c.

That may have been a typo. I found getsm.c at
http://www.iedu.com/mrd/c

[Memory failure] Thanks, Bill.

(getsmx.c in the same directory takes advantage of gcc's
extension to permit nested function definitions [which has
nothing to do with this thread, but is relevent to one of the
others currently active]).

My apologies to everyone who got the 404 error. Now if I could
just remember where I left my glasses...

--
Morris Dovey
West Des Moines, Iowa USA
C links at http://www.iedu.com/c

[LibraryUser]

Joona I Palaste wrote:

LibraryUser <de**********@made.invalid> scribbled the following:

Joona I Palaste wrote:

LibraryUser <de**********@made.invalid> scribbled the following:
> Joona I Palaste wrote:
>> LibraryUser <de**********@made.invalid> scribbled the following:
>> >>
>> >> [...]
>>
>> > No it isn't (difficult). It just isn't part of standard C.
>> > Pascal and Ada routinely implement it, and it is an available
>> > (non-portable) extension under GCC.
>>
>> It's hard to even specify how nested functions should work in C.
>> This is because of function pointers. Suppose you got hold of a
>> function pointer pointing to a nested inner function, outside of
>> the enclosing outer function. This nested inner function would
>> then access variables defined in the outer function - what then?

> In Pascal, at least, this is handled in a similar manner to C
> handling of pointers to local variables - they are illegal once
> the enclosing scope is no longer active. Of course Pascal
> doesn't have pointers to functions, just references to them, but
> the principle is the same.

In C, indirecting through a pointer which is pointing at something
not in scope any more is undefined behaviour. What is it in Pascal?
A run-time error?

Pascal attempts to diagnose errors at compile time. Since it
doesn't have function pointers, but only the ability to pass
functions to other functions, that function has to be in scope at
the call. Thus the problem never arises.

Some people consider this sort of attitude restrictive; I
consider it extremely helpful. I believe extended (ISO10206)
Pascal has further provisions, but am not certain. For example,
limiting function pointers to global procedures would suffice.
Since all C functions/procedures are global, this automatically
applies to C. (for a reasonable meaning of global).

A-aga... doesn't Pascal have pointers to scalars (integers etc.)
just like C does? What happens if a Pascal function returns a
pointer pointing to an integer outside of scope, and then the
calling procedure or function indirects through that pointer?

All Pascal pointers are those returned by new, which is the
equivalent of malloc. They can be copied, but not altered.
There is no pointer arithmetic. To handle ordinary variables
they may be passed either by value (default) or by reference (a
VAR designation, as in "myproc(VAR myvar : integer);", which is
set in the called functions "prototype". Thus all pointers can
be checked at run time.

This leaves the problem of dangling pointers, i.e. copies of
pointers that have been "freed" (with "dispose" in Pascal).
These are also runtime checkable, but the effort may be
excessive.

Before anybody starts screaming OT, this is presented to contrast
the languages and the usage thought processes. The objectives of
the languages are different. Things that are arranged to "not
get in the way" in C prevent compile time (and often run time)
validation. Things in Pascal are specifically arranged to
facilitate compile and run time validation.

--
Replies should be to the newsgroup
Chuck Falconer, on vacation.

[Dave Thompson]

On 7 Sep 2003 16:13:32 GMT, Joona I Palaste <pa*****@cc.helsinki.fi>
wrote:

LibraryUser <de**********@made.invalid> scribbled the following:

Joona I Palaste wrote:

LibraryUser <de**********@made.invalid> scribbled the following: <snip: nested functions (etc.) and upward closures> > In Pascal, at least, this is handled in a similar manner to C
> handling of pointers to local variables - they are illegal once
> the enclosing scope is no longer active. Of course Pascal
> doesn't have pointers to functions, just references to them, but
> the principle is the same.

In C, indirecting through a pointer which is pointing at something
not in scope any more is undefined behaviour. What is it in Pascal?
A run-time error?

Actually in standard Pascal you can't form a pointer to a local
variable, only to allocated aka heap space, although it is a common(?)
extension. And yes, it is the equivalent of Undefined Behavior (not
required to be diagnosed, and AFAIK typically not diagnosed) to
indirect through a pointer to either allocated space which has been
dispose'd or a (local) variable which has gone out of scope.
Pascal attempts to diagnose errors at compile time. Since it
doesn't have function pointers, but only the ability to pass
functions to other functions, that function has to be in scope at
the call. Thus the problem never arises.

Some people consider this sort of attitude restrictive; I
consider it extremely helpful. I believe extended (ISO10206)
Pascal has further provisions, but am not certain. For example,
limiting function pointers to global procedures would suffice.
Since all C functions/procedures are global, this automatically
applies to C. (for a reasonable meaning of global).

A-aga... doesn't Pascal have pointers to scalars (integers etc.) just
like C does? What happens if a Pascal function returns a pointer
pointing to an integer outside of scope, and then the calling procedure
or function indirects through that pointer?

Pascal has pointers to all data types, both scalar and composite
(arrays, records, etc.), but not to functions -- or procedures, which
are classified separate in Pascal, as in Ada and (the equivalent) in
Fortran; there is no standard Pascal term that covers both, but both
Fortan and Ada use subprogram, so I will. Since you can't declare a
pointer to subprogram, you can't return one or store it explicitly.

What you can have, as Chuck indicates, is in effect a reference -- a
subprogram parameter which is itself of subprogram "type", but using a
special syntax, not a nameable type, and is called with an actual
(necessarily named) subprogram of appropriate type, which is then used
(called) where the parameter is used. But parameter passing only
works downward (to inner nesting) so it cannot reach a point where the
outer activations needed by the actual subprogram are gone.

In Ada, by contrast, you can have access (their pointer) to
subprogram, as you can to data, but you can't have any access
variable, or even the access type, at a nesting level lower (that is,
outer) than the variables or subprograms you use it to point to --
normally; you can override this for variables with Unchecked_Access,
and for subprograms using Unchecked_Conversion or in GNAT
Unrestricted_Access, in which case you are responsible for the
possibly bogus and undiagnosed results. And for "normal" accesses
that point to allocated/heap space Ada discourages *any* freeing
(Unchecked_Deallocation) which evades the issue of stale pointers.

- David.Thompson1 at worldnet.att.net