«

I am writing binary tree programs using non-recursion and recursion to
understand the differences and pros and concs. Here, I am trying to do
a post-order traversal using recursion and non-recusion.

While I can write recusive version more simplistically, for writing
the non-recusive I have to store an extra state called visited.

Here is my code for non recusive.

typedef node {
int data;
node *left;
node *right;
int visited = 0;
} node;

/*
Assuming you have a stack setup with push() and pop() operations.
Also assuming that all nodes are initially marked to 0.
(This function will reset them back to zero when finished)
*/
void postorder(Node *n) {
push(n);

while (stack.size > 0) {
n = (Node*)pop();

if (n->marked || (n->left == NULL && n->right == NULL)) {
n->marked = 0;
printf("%d\n", n->value);
}
else {
n->marked = 1;
push(n);

if (n->right) push(n->right);
if (n->left) push(n->left);
}
}
}

And this is my recusive version which is lot simpler and elegant.

void postorder( node *node){
if (node){
postorder(node->left);
postorder(node->right);
printf("%d", node->data);
} else
return;
}


Can you please tell me if we can even write a non-recusive function
without the extra flag visited. I want to minimize the extra overhead.

When should we use recusion and when should we not ? What is the
maximum recursion depth of a gcc compiler ? I am trying to learn to
write better code and these are the questions which are not answered
in my mind. Please help.

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Krypto wrote:
> I am writing binary tree programs using non-recursion and recursion to
> understand the differences and pros and concs. Here, I am trying to do
> a post-order traversal using recursion and non-recusion.
>
> While I can write recusive version more simplistically, for writing
> the non-recusive I have to store an extra state called visited.
>
> Here is my code for non recusive.
>
> typedef node {
> int data;
> node *left;
> node *right;
> int visited = 0;
> } node;
>
> /*
> Assuming you have a stack setup with push() and pop() operations.
> Also assuming that all nodes are initially marked to 0.
> (This function will reset them back to zero when finished)
> */
> void postorder(Node *n) {
> push(n);
>
> while (stack.size > 0) {
> n = (Node*)pop();
>
> if (n->marked || (n->left == NULL && n->right == NULL)) {
> n->marked = 0;
> printf("%d\n", n->value);
> }
> else {
> n->marked = 1;
> push(n);
>
> if (n->right) push(n->right);
> if (n->left) push(n->left);
> }
> }
> }
>
> And this is my recusive version which is lot simpler and elegant.
>
> void postorder( node *node){
> if (node){
> postorder(node->left);
> postorder(node->right);
> printf("%d", node->data);
> } else
> return;
> }
>
>
> Can you please tell me if we can even write a non-recusive function
> without the extra flag visited. I want to minimize the extra overhead.
>
> When should we use recusion and when should we not ? What is the
> maximum recursion depth of a gcc compiler ? I am trying to learn to
> write better code and these are the questions which are not answered
> in my mind. Please help.

In most implementations I can think of, the limitation on recursion is
more one of stack than of the compiler. One extra flag will consume a
lot less memory than using recursion would.

As I'm sure you know, every time you recurse, a new stack frame is
pushed, containing the arguments to the function &c.

- --
- --Falcon Darkstar Kirtaran
- --
- --OpenPGP: (7902:4457) 9282:A431

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iQIcBAEBAgAGBQJJdiwcAAoJEKmxP9YxEE4rmHoQAKfhH0VXTZ XDZZkA3zmtQbwo
gA7Tjqwhsius9WTWhgR70rOcIjddzIZqywds/6px1Uqf6sM+dVp1M6aIC2Nh2KwM
DdBPx3soU3Pwzcc2VBIGneefDSgs1C3cK16k/1FIXCQ9vpFr4NaMA/S4QvKGev6T
HBh4OW7NRpuH2DSfP84Q/qYmjuytci5tRl9hj3MT3GcR65zVP4OtpOdTPe9dvsYa
zVufSb9ssL4Cc+K5GJJgIcfrCeV+wl+pO5Tu4IF79nj0GP86IK cSzeG06AOlxmpL
wL45nRWxNy6hWd8ksUxjS/QhprgvQAhl4Zy+PCorE6aaxgjuuwdKrvSKc0u3H36r
IHTChcBB9motW/D2085m0i/fY5DB1EL7KFP6c6cjfVwy+SMbhDeWgX5UxoYE5SqZ
E0Fe75W7BTh7Vvh7POsY25okEuO0DFAs8gWUOCTOP07JddNPuD KPOcfWPQPfZDUl
aBEYCvlEblTC0a7MQz6oW0PTCviHjaSdrTgvglRzWtPG72Ku1t TKBxqLUQ0DWcvQ
NOUoE0y0YLKu5zuvatx0Bt+m6+HoWFx3/7P8fR3BwFZD8OLoNpMAeSw7Eq5qe19L
mhc5GGSDjSr4BPcDBmf6dKZjSHN9IK+TQ5BHd92B0xaHCIthUZ BNjKP4oNMa4yIZ
MhVaFlzWzqC/EjHiTDZx
=wdwa
-----END PGP SIGNATURE-----

> In most implementations I can think of, the limitation on recursion is
> more one of stack than of the compiler. *One extra flag will consume a
> lot less memory than using recursion would.
>
> As I'm sure you know, every time you recurse, a new stack frame is
> pushed, containing the arguments to the function &c.
>
> - --
> - --Falcon Darkstar Kirtaran

So would you say that my iterative code is more efficient than
recursive. So how can one distinguish when to use recusion and when
not to.

All recusive function can be written in iterative way, then why even
use recusion. I could only think of ease of code writing. Anything
else I am missing ?

Thanks

Krypto wrote:
>> In most implementations I can think of, the limitation on recursion is
>> more one of stack than of the compiler. One extra flag will consume a
>> lot less memory than using recursion would.
>>
>> As I'm sure you know, every time you recurse, a new stack frame is
>> pushed, containing the arguments to the function &c.
>
> So would you say that my iterative code is more efficient than
> recursive.

"Efficient" in what way? There are many, many competing metrics, and
you have to specify which one you want to optimize for.

An iterative implementation is likely to be more efficient in its use of
memory, but the difference will be negligible in most cases; you'd need
a tree hundreds or even thousands of levels deep before you noticed on
most modern machines. (OTOH, if you're coding for a toaster, even a
half-dozen levels may exceed the stack space available...)

> So how can one distinguish when to use recusion and when not to.

That's a matter of opinion. IMHO, you should always use recursion where
you have the option, unless doing so pushes you up against the
implementation's call depth limit.

> All recusive function can be written in iterative way, then why even
> use recusion. I could only think of ease of code writing. Anything
> else I am missing ?

Recursion is easier to understand (and thus code correctly) than
iteration. Correctness and ease of maintenance should be your top two
priorities as a programmer; let the compiler worry about small
optimizations, and don't bother with the big ones (which involve
algorithm changes) until testing shows performance is actually a
problem. It's a lot easier to make correct code faster than it is to
make fast code more correct...

S

--
Stephen Sprunk "Stupid people surround themselves with smart
CCIE #3723 people. Smart people surround themselves with
K5SSS smart people who disagree with them." --Isaac Jaffe

Krypto wrote:
> I am writing binary tree programs using non-recursion and recursion to
> understand the differences and pros and concs. Here, I am trying to do
> a post-order traversal using recursion and non-recusion.
>
> While I can write recusive version more simplistically, for writing
> the non-recusive I have to store an extra state called visited.
>
> Here is my code for non recusive.
>
> typedef node {
> int data;
> node *left;
> node *right;
> int visited = 0;
> } node;
>
> /*
> Assuming you have a stack setup with push() and pop() operations.
> Also assuming that all nodes are initially marked to 0.
> (This function will reset them back to zero when finished)
> */
> void postorder(Node *n) {
> push(n);
>
> while (stack.size > 0) {
> n = (Node*)pop();
>
> if (n->marked || (n->left == NULL && n->right == NULL)) {
> n->marked = 0;
> printf("%d\n", n->value);
> }
> else {
> n->marked = 1;
> push(n);
>
> if (n->right) push(n->right);
> if (n->left) push(n->left);
> }
> }
> }
>
> ...
> Can you please tell me if we can even write a non-recusive function
> without the extra flag visited. I want to minimize the extra overhead.

I'll take a stab at it (untested):

typedef node {
int data;
node *left;
node *right;
node *parent;
} node;

void postorder(Node *n) {
Node *cur = n, *last = n;

while (cur) {
/* ascending from the right (or dead end)? */
if (last == cur->right) {
printf("%d\n", cur->data);
last = cur;
cur = cur->parent;
continue;
}

/* ascending from the left? */
if (last == cur->left) {
/* can we descend to the right? */
if (cur->right) {
last = cur;
cur = cur->right;
} else {
/* switch to ascending */
last = NULL;
}
continue;
}

/* we must be descending */

/* try to the left */
if (cur->left) {
last = cur;
cur = cur->left;
continue;
}

/* try to the right */
if (cur->right) {
last = cur;
cur = cur->right;
continue;
}

/* switch to ascending */
last = NULL;
continue;
}
}

This assumes a parent link in the Node, which you may not have, but it's
useful for many other things so I usually have one. You can also fake
it with push/pop, but I'll leave that as an exercise for the reader.

> What is the maximum recursion depth of a gcc compiler ?

The maximum recursion depth is not limited by the compiler; it's limited
by the execution environment, and it's tough to give a maximum other
than say.

S

--
Stephen Sprunk "Stupid people surround themselves with smart
CCIE #3723 people. Smart people surround themselves with
K5SSS smart people who disagree with them." --Isaac Jaffe

On 20 Jan, 21:16, Stephen Sprunk <step...@sprunk.org> wrote:
> Krypto wrote:

> >> In most implementations I can think of, the limitation on recursion is
> >> more one of stack than of the compiler. *One extra flag will consume a
> >> lot less memory than using recursion would.
>
> >> As I'm sure you know, every time you recurse, a new stack frame is
> >> pushed, containing the arguments to the function &c.
>
> > So would you say that my iterative code is more efficient than
> > recursive.
>
> "Efficient" in what way? *There are many, many competing metrics, and
> you have to specify which one you want to optimize for.
>
> An iterative implementation is likely to be more efficient in its use of
> memory, but the difference will be negligible in most cases; you'd need
> a tree hundreds or even thousands of levels deep before you noticed on
> most modern machines. *(OTOH, if you're coding for a toaster, even a
> half-dozen levels may exceed the stack space available...)
>
> > So how can one distinguish when to use recusion and when not to.
>
> That's a matter of opinion. *IMHO, you should always use recursion where
> you have the option, unless doing so pushes you up against the
> implementation's call depth limit.

since any iteration can be replaced with recusion do you really
have no fors or whiles in your programs?


> > All recusive function can be written in iterative way, then why even
> > use recusion.

it gets harder when it's no longer tail recursive (eg. the tree
example).
You end up implementing a stack in your program. Why not use the
call stack?

> > I could only think of ease of code writing. Anything
> > else I am missing ?

seems like a pretty good reason to me

> Recursion is easier to understand (and thus code correctly) than
> iteration.

this is a matter of opinion. A tree walk I'd use recursion.
A linked list it hardly matters (I'd probably use recusion now,
but less so in the past). Recursive descent parsing is clear
and easy to code.


> *Correctness and ease of maintenance should be your top two
> priorities as a programmer;

my usual prime metrics, though its easy to dream
up special circumstances (even for "correctness"!)

> let the compiler worry about small
> optimizations, and don't bother with the big ones (which involve
> algorithm

no. Try to choose clear algorthms with reasonable performance
at coding time. There is never an excuse for bubble sort.

>*It's a lot easier to make correct code faster than it is to
> make fast code more correct...


--
Nick Keighley

The phrase "we (I) (you) simply must--" designates something
that need not be done. "That goes without saying" is a red warning.
"Of course" means you had best check it yourself. These
small-change cliches and others like them, when read correctly,
are reliable channel markers.
Lazerus Long

Stephen Sprunk <> writes:

> Krypto wrote:
>>> In most implementations I can think of, the limitation on recursion is
>>> more one of stack than of the compiler. One extra flag will consume a
>>> lot less memory than using recursion would.
>>>
>>> As I'm sure you know, every time you recurse, a new stack frame is
>>> pushed, containing the arguments to the function &c.
>>
>> So would you say that my iterative code is more efficient than
>> recursive.
>
> "Efficient" in what way? There are many, many competing metrics, and
> you have to specify which one you want to optimize for.
>
> An iterative implementation is likely to be more efficient in its use
> of memory, but the difference will be negligible in most cases; you'd
> need a tree hundreds or even thousands of levels deep before you
> noticed on most modern machines. (OTOH, if you're coding for a
> toaster, even a half-dozen levels may exceed the stack space
> available...)

This is total nonsense Stephen. Always consider efficiency. As a
designer and programmer you are not doing your job if you do not. Your
program is one of MANY running on a modern multi-tasking OS and if you
take your rather wasteful design ideas then we would have ... oh ! We
do! Programs taking as long to start now as they did 10 years ago ....

When programming in C efficiency should ALWAYS be a consideration. Well,
almost always. There is a level of thought that says you should never
consider optimisation early in a program. I think that is bullshit and
you should always consider potential program execution path and data
structure from the point of view of efficiency in terms of execution
time and memory usage. If you really dont care then use Python ......

>
>> So how can one distinguish when to use recusion and when not to.
>
> That's a matter of opinion. IMHO, you should always use recursion
> where you have the option, unless doing so pushes you up against the
> implementation's call depth limit.

Again nonsense IMO. Purely from a maintenance and efficiency point of
view iteration is likely to be faster than recursion in most cases where
you could potentially use recursion. e.g consider a recursive strcpy and
the amount of stack written and read as opposed to one memory location
read and written.

>
>> All recusive function can be written in iterative way, then why even
>> use recusion. I could only think of ease of code writing. Anything
>> else I am missing ?
>
> Recursion is easier to understand (and thus code correctly) than
> iteration. Correctness and ease of maintenance should be your top two

Wow. You have just rewritten the rule books. In my reasonably
considerable experiences of working on large projects, recursion
frequently baffled people and was harder to debug than plain simple
iteration. Most CPUs have special decrement and jump if not zero type
command to speed up iterations, most people think in terms of iteration
easier.


> priorities as a programmer; let the compiler worry about small
> optimizations, and don't bother with the big ones (which involve
> algorithm changes) until testing shows performance is actually a
> problem. It's a lot easier to make correct code faster than it is to
> make fast code more correct...
>
> S

No one said "fast" but using recursion where simple iteration will do is
not making "fast complicated code". Little if anything is easier to
follow than simple iteration - especially not recursion.

I would be interested to hear about compilers replacing recursion with
iterative statements for efficiency.

The basic disagreement we have is your claim that recursion is easier
than iteration. I believe that to be false generally except for the few
text book cases.

The oft stated mantra about "easier to make correct code faster" has a
basic fault - maybe it wasn't necessary to make correct slow code in the
first place? Consider correct efficient code from the dawning of the
project.

It IS far harder to make correct, slow code faster if the overall design
and data structures need to be overhauled in a LARGE project to afford
some necessary optimisations at a later date.

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Krypto wrote:
>> In most implementations I can think of, the limitation on recursion is
>> more one of stack than of the compiler. One extra flag will consume a
>> lot less memory than using recursion would.
>>
>> As I'm sure you know, every time you recurse, a new stack frame is
>> pushed, containing the arguments to the function &c.
>>
>> - --
>> - --Falcon Darkstar Kirtaran
>
> So would you say that my iterative code is more efficient than
> recursive. So how can one distinguish when to use recusion and when
> not to.
>
> All recusive function can be written in iterative way, then why even
> use recusion. I could only think of ease of code writing. Anything
> else I am missing ?
>
> Thanks

Not all recursive code can be written iteratively.

Many optimizing compilers, on finding a use of recursion they know how
to make iterative, will change the code. Recursion is only better if
there is no alternative or if you care more about readability than
efficiency.

- --
- --Falcon Darkstar Kirtaran
- --
- --OpenPGP: (7902:4457) 9282:A431

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iQIcBAEBAgAGBQJJd0fPAAoJEKmxP9YxEE4rdMAP/1QdHx3/R/FPt1vOWN4SU3i/
8yBHe9ZC/0CCphskaim5rc4vdmC3V953c3LPr6MHql5WTkjbaGbsf9fMv7u S9Y4Z
VaqtNOAmEXOjQ9UnF5u/bSxL4miRQGEEV3vAWunMtbFo6bBLQnCZmibnn0OWci+N
g4cdyS8QCCD/OXIHiRfOd+d2KF09e/cZwar/4pMVZYykVRagQMy3Z3rDGaCc7t1f
qv9ffnNEDHdMSc903/dCWMRLAUz9RH7CLFo1O31p4fOzYBD2gChBpQyf+vgfaX4U
V+Njq3xTvBt0/7jyaOy5aT9kIk4bu/TiD6U5FS9O424fR6Vu9Tfhzc1xOKewIQA1
yMgm9p4izKT0ac/Wyc26mHUXHzJxQZOBcleiLPIYt2A+4PvzeVaziJDpIwt2VP9k
g+x4UI9ytV9Hp3I2fob+VPQjz1Nvze8IHDkEPHIiZte0q16Rum 4h+iPAVoBHsvgr
1xyXE/7DLmBhsnsOHqMXE9mwS9swN++/Cml9u5nap97tl1Jz+swe9LHSSDTgjEWA
k1zwWDroP9dfOB1AbEj9PohD3wJ9CB7QGPgT1q2gfgLQ0v/TdYaUy3yUPEFAtmxR
LvRQvedSVfuK7vX0gxmgFYnTZwI93jXF/VObMAjLMzGyQNzAmYSwIpGsLm7MDf2L
gHYOgj/rK10s3V6b0Yrr
=MfED
-----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Stephen Sprunk wrote:
> Krypto wrote:
>>> In most implementations I can think of, the limitation on recursion is
>>> more one of stack than of the compiler. One extra flag will consume a
>>> lot less memory than using recursion would.
>>>
>>> As I'm sure you know, every time you recurse, a new stack frame is
>>> pushed, containing the arguments to the function &c.
>>
>> So would you say that my iterative code is more efficient than
>> recursive.
>
> "Efficient" in what way? There are many, many competing metrics, and
> you have to specify which one you want to optimize for.
>
> An iterative implementation is likely to be more efficient in its use of
> memory, but the difference will be negligible in most cases; you'd need
> a tree hundreds or even thousands of levels deep before you noticed on
> most modern machines. (OTOH, if you're coding for a toaster, even a
> half-dozen levels may exceed the stack space available...)
>
>> So how can one distinguish when to use recusion and when not to.
>
> That's a matter of opinion. IMHO, you should always use recursion where
> you have the option, unless doing so pushes you up against the
> implementation's call depth limit.
>
>> All recusive function can be written in iterative way, then why even
>> use recusion. I could only think of ease of code writing. Anything
>> else I am missing ?
>
> Recursion is easier to understand (and thus code correctly) than
> iteration. Correctness and ease of maintenance should be your top two
> priorities as a programmer; let the compiler worry about small
> optimizations, and don't bother with the big ones (which involve
> algorithm changes) until testing shows performance is actually a
> problem. It's a lot easier to make correct code faster than it is to
> make fast code more correct...
>
> S
>

Are you mad? The entire study of theoretical computer science is based
on algorithm changes to improve efficiency. Also there are many cases
recursion is harder to understand (and less concise) than iteration.

I agree that micro-optimization is pointless, though, unless you're
writing an optimizing compiler.

- --
- --Falcon Darkstar Kirtaran
- --
- --OpenPGP: (7902:4457) 9282:A431

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iQIcBAEBAgAGBQJJd0hqAAoJEKmxP9YxEE4rlN8P+wSqtivVEc xq9VmjfqFt2+3t
uPtAqYwBgHna+BrY60ra3iIhBcHZDHxYIdO5kiV/sjNTg3K6Hnmn1e4oTfOa7BpH
LgNcVw5TF5jebDou5byQG65XIEAXWb89Iyx+QZ+dgMFaAIDaoL XdNj4rA6klnH4Q
7970lJsfGaRP3WD7p/GRh+cQsrl6jNNf4SVLH9h6+avGCGifowvxbp669P8Yurlj
PUiQv5ut+Ts+TdLu6tcTzRqWU5gzn/YLbHCAApn4ksnJJe+xkqL1iQyx5Qo6n+3a
hvV+fUqlnTYIJL/nX2WANTL+WQNSud6fHySxmI91/vBpdyf9fDQTjOTY0MxB/4wm
KsjYj8gL6UwkXZfI6lvROvrpfoYfsFKn2Q4oCeQmXujO07rBRw 8CuNLjkuvK3hLL
mROX9BuzOlr5WjOvC/yG0DEgDFKpcrGhtXSP73b+1ZCnf5lMTy7yF8cKO+6P38Xu
9PGog9EeiGazlVlaCdLJr7RXAB7T5Zx2oHJ164g+5mRSVdyKOR RZof0N6tSRJs33
BigNxZzzF+ZqSXyZrJ51wEi5JuKK8rbTd0y8aNW0nfBjVWf137 KB4B93rYKfzIbr
H8AQygZqF0x1FPyUumllUNGm3+REMfzVFIkDPJ8C2gXwTDnHSv WiyVES+vscEYKB
WQS/mnF2UbOkD8nwoNK8
=qPkh
-----END PGP SIGNATURE-----

Falcon Kirtaran <> writes:
[...]
> Not all recursive code can be written iteratively.
[...]

Yes, it can; I believe there's a theorem to that effect. (You often
have to implement an explicit stack to do it.)

--
Keith Thompson (The_Other_Keith) kst- <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"