Suggestions on improving program on binary tree postorder traversal

[Krypto]

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.

 

[Falcon Kirtaran]

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

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

iQIcBAEBAgAGBQJJdiwcAAoJEKmxP9YxEE4rmHoQAKfhH0VXTZXDZZkA3zmtQbwo
gA7Tjqwhsius9WTWhgR70rOcIjddzIZqywds/6px1Uqf6sM+dVp1M6aIC2Nh2KwM
DdBPx3soU3Pwzcc2VBIGneefDSgs1C3cK16k/1FIXCQ9vpFr4NaMA/S4QvKGev6T
HBh4OW7NRpuH2DSfP84Q/qYmjuytci5tRl9hj3MT3GcR65zVP4OtpOdTPe9dvsYa
zVufSb9ssL4Cc+K5GJJgIcfrCeV+wl+pO5Tu4IF79nj0GP86IKcSzeG06AOlxmpL
wL45nRWxNy6hWd8ksUxjS/QhprgvQAhl4Zy+PCorE6aaxgjuuwdKrvSKc0u3H36r
IHTChcBB9motW/D2085m0i/fY5DB1EL7KFP6c6cjfVwy+SMbhDeWgX5UxoYE5SqZ
E0Fe75W7BTh7Vvh7POsY25okEuO0DFAs8gWUOCTOP07JddNPuDKPOcfWPQPfZDUl
aBEYCvlEblTC0a7MQz6oW0PTCviHjaSdrTgvglRzWtPG72Ku1tTKBxqLUQ0DWcvQ
NOUoE0y0YLKu5zuvatx0Bt+m6+HoWFx3/7P8fR3BwFZD8OLoNpMAeSw7Eq5qe19L
mhc5GGSDjSr4BPcDBmf6dKZjSHN9IK+TQ5BHd92B0xaHCIthUZBNjKP4oNMa4yIZ
MhVaFlzWzqC/EjHiTDZx
=wdwa
-----END PGP SIGNATURE-----

 

[Krypto]

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

 

[Stephen Sprunk]

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]

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

 

[Guest]

Krypto wrote:


"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...)


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?


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?

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

 

[Richard]

"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 ......

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.

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.

 

[Falcon Kirtaran]

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

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/0CCphskaim5rc4vdmC3V953c3LPr6MHql5WTkjbaGbsf9fMv7uS9Y4Z
VaqtNOAmEXOjQ9UnF5u/bSxL4miRQGEEV3vAWunMtbFo6bBLQnCZmibnn0OWci+N
g4cdyS8QCCD/OXIHiRfOd+d2KF09e/cZwar/4pMVZYykVRagQMy3Z3rDGaCc7t1f
qv9ffnNEDHdMSc903/dCWMRLAUz9RH7CLFo1O31p4fOzYBD2gChBpQyf+vgfaX4U
V+Njq3xTvBt0/7jyaOy5aT9kIk4bu/TiD6U5FS9O424fR6Vu9Tfhzc1xOKewIQA1
yMgm9p4izKT0ac/Wyc26mHUXHzJxQZOBcleiLPIYt2A+4PvzeVaziJDpIwt2VP9k
g+x4UI9ytV9Hp3I2fob+VPQjz1Nvze8IHDkEPHIiZte0q16Rum4h+iPAVoBHsvgr
1xyXE/7DLmBhsnsOHqMXE9mwS9swN++/Cml9u5nap97tl1Jz+swe9LHSSDTgjEWA
k1zwWDroP9dfOB1AbEj9PohD3wJ9CB7QGPgT1q2gfgLQ0v/TdYaUy3yUPEFAtmxR
LvRQvedSVfuK7vX0gxmgFYnTZwI93jXF/VObMAjLMzGyQNzAmYSwIpGsLm7MDf2L
gHYOgj/rK10s3V6b0Yrr
=MfED
-----END PGP SIGNATURE-----

 

[Falcon Kirtaran]

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

"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...)


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.


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+wSqtivVEcxq9VmjfqFt2+3t
uPtAqYwBgHna+BrY60ra3iIhBcHZDHxYIdO5kiV/sjNTg3K6Hnmn1e4oTfOa7BpH
LgNcVw5TF5jebDou5byQG65XIEAXWb89Iyx+QZ+dgMFaAIDaoLXdNj4rA6klnH4Q
7970lJsfGaRP3WD7p/GRh+cQsrl6jNNf4SVLH9h6+avGCGifowvxbp669P8Yurlj
PUiQv5ut+Ts+TdLu6tcTzRqWU5gzn/YLbHCAApn4ksnJJe+xkqL1iQyx5Qo6n+3a
hvV+fUqlnTYIJL/nX2WANTL+WQNSud6fHySxmI91/vBpdyf9fDQTjOTY0MxB/4wm
KsjYj8gL6UwkXZfI6lvROvrpfoYfsFKn2Q4oCeQmXujO07rBRw8CuNLjkuvK3hLL
mROX9BuzOlr5WjOvC/yG0DEgDFKpcrGhtXSP73b+1ZCnf5lMTy7yF8cKO+6P38Xu
9PGog9EeiGazlVlaCdLJr7RXAB7T5Zx2oHJ164g+5mRSVdyKORRZof0N6tSRJs33
BigNxZzzF+ZqSXyZrJ51wEi5JuKK8rbTd0y8aNW0nfBjVWf137KB4B93rYKfzIbr
H8AQygZqF0x1FPyUumllUNGm3+REMfzVFIkDPJ8C2gXwTDnHSvWiyVES+vscEYKB
WQS/mnF2UbOkD8nwoNK8
=qPkh
-----END PGP SIGNATURE-----

 

[Keith Thompson]

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.)

 

[Ben Pfaff]

Not all recursive code can be written iteratively.

And yet it can run on CPUs that have no explicit support for
recursion. Amazing!

 

[jameskuyper]

Falcon Kirtaran wrote:
....

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've never studied computer science formally; my major was in physics.
However, I was under the impression that a significant portion of
computer science dealt with things other than efficiency, such as
writing code that is easy to understand, easy to maintain, and easy to
verify the correctness of. Am I mistaken? If so, I strongly recommend
expanding the curriculum, because unmaintainable code has caused me,
at least, far more grief than inefficient code ever has.

 

[Falcon Kirtaran]

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

Falcon Kirtaran wrote:
...

I've never studied computer science formally; my major was in physics.
However, I was under the impression that a significant portion of
computer science dealt with things other than efficiency, such as
writing code that is easy to understand, easy to maintain, and easy to
verify the correctness of. Am I mistaken? If so, I strongly recommend
expanding the curriculum, because unmaintainable code has caused me,
at least, far more grief than inefficient code ever has.

It is a factor, but the only way to extend our computational
capabilities without all the time procuring new hardware is to make more
efficient algorithms, particularly for one-off coding for computational
stuff. Comments can help a lot for making maintainable code, as can
documentation, and not micro-optimization.

- --
- --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

iQIcBAEBAgAGBQJJd14oAAoJEKmxP9YxEE4r07IQALk2MqyTblMIsUnvyZ02lxCg
E18BqAjcbArZmL0YDIL3BUA1OLWji1AjcV7pf2ZB8o5bHQY3A4ex5AotOBh4CzON
ex8JlxjUYxGYSA9YeQs1Y2WJkTRPr3oUZpNv/4PNHDqo3iQCLQP51oZnP4L2WYGd
jJzAKyD/dE/3z+GZKrFoPecDarlzv7ad79ZG9dV8Tq8s9KBNwawJ+4KxePD3yGNi
woECOV69q/bbWK8zXQbkBSJxZEMPRb+bwMgky7J3Bqh5TF0VuMcx5TihWxmdnzz7
Uf47ISA49DWCEYjhPP/CJ4nfZbflFVn7M8CZwTWRIyM71e8AD1/6pHIWcaUk9fEx
YyK8aN/9HtKEeq8zMv+ln6VUm66t+oXsjzCeBA+DLwkAZ6aAdpG2hOdh64b50EVj
3T2+ZeCOBPyegTRnb+0joCLQ8ES7669n7GgeRS1Gu36fUmZoei67qk34cFldM0wO
gytHTVNTzCr/IA8LJLMjeD7JLNkWBtFms/a7CQqmXCGQYBuaTGdhl6d+ufWrgzst
u3OihTVrkjrYCwy1ED/O+Z6dkHie1dIafGhhVlIZWrEBl7jXpCBNA2jvOEIYhS3+
zaHf2VN2t5Zc+fzpQ3yRPHGbYZ5HnFgQmc5KcB5HxoPpugyb61loqwwHCGp+SrDm
/Ebad+Z8zX8PkxVW9DvZ
=r/5D
-----END PGP SIGNATURE-----

 

[Nate Eldredge]

Falcon Kirtaran wrote:
...

I've never studied computer science formally; my major was in physics.
However, I was under the impression that a significant portion of
computer science dealt with things other than efficiency, such as
writing code that is easy to understand, easy to maintain, and easy to
verify the correctness of. Am I mistaken? If so, I strongly recommend
expanding the curriculum, because unmaintainable code has caused me,
at least, far more grief than inefficient code ever has.

That would fall under the heading of "practical computer science".
Theoretical computer science is concerned mainly with the possibility of
solving abstract computational problems, abstract algorithms for doing
so when possible, and the (asymptotic) efficiency of those algorithms.
A typical computer science curriculum will include both, and usually
much more of the former than the latter.

 

[Falcon Kirtaran]

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

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.)

Yes, I should have added, "without implementing a stack".

- --
- --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

iQIcBAEBAgAGBQJJd16VAAoJEKmxP9YxEE4rhTEQAKyBH3WuEuI7d3WGAwBBpXa0
YdAHfNo0+W+uBhkFfqx0BME7+XAfIkpF2bWMOp1rLtPymOc5GRFklStWKdSJnP/a
LTYDX4SeI9ji3WkAUjEK86ljWToRvwAlWwFxMLPWFQKJdQYEcpXgm75pqFcu9f6h
Bv7r1TaPCCE+IR8RC39dx3XLZH+bo/zG1zc4w2B4THjDXyr5Uu90A+Z2SmQLAqX7
7hgc3FDLWQRK+WkUDLZbleaC9ZwRJrH0i++6IOwRFfs+skcKXgmMJP8lOVgKl5l1
snxZdF5QIWCInoLw0nVJVTCNmnQZ1Pp1pc6dx55mAHE2Kq+FaMP27d0rq5aB9jVr
PqAbh5WtOgMRDdHtk0M8UcfP2+F8dgW+GGLA16srv+cKAFzm7qjQt5Wp6REtjVDw
FhhtY0F58rKgiFt95IARBKbdlr40Wryt+IJdQL6pTxjkqhDrRulQL2lRMleRlM2Y
PbJvfaqhIS0yBMf7K1O9BzQRjOHzUZXkbHiUU6STP37seFUyFENLaELNm7ldxNx1
YyIj/VJzcPNul9sP0dSCVm3NxsQ08bzp5Hy+S2+L+7oOSc4t/mqH7fblkzLk2WF7
rffMjiE/UQl2qimn/DR+zqNhf3V1n2pLshCB7GopyQp6TnvkVdLPYvmkd8l5/bqb
HQdMRFaaVa7AXbx6OUwP
=uWYA
-----END PGP SIGNATURE-----

 

[Keith Thompson]

Falcon Kirtaran wrote:
...

I've never studied computer science formally; my major was in physics.
However, I was under the impression that a significant portion of
computer science dealt with things other than efficiency, such as
writing code that is easy to understand, easy to maintain, and easy to
verify the correctness of. Am I mistaken? If so, I strongly recommend
expanding the curriculum, because unmaintainable code has caused me,
at least, far more grief than inefficient code ever has.

There's a difference between computer *science* and computer
programming (though computer science curricula typically attempt to
teach the latter as well). As Edsger Dijkstra famously said, "Computer
science is no more about computers than astronomy is about
telescopes."

Analysis of algorithms, including things like big-O notation, is
definitely part of (theoretical) computer science.

 

[Tim Rentsch]

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

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.)

Yes, I should have added, "without implementing a stack".

An empty statement if no definition of "stack" is given,
or what is meant by "implementing" one.