By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,984 Members | 1,423 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,984 IT Pros & Developers. It's quick & easy.

programming style: which is clearer? (iteration vs. recursion)

P: n/a
I'm trying to decide which of the following programming styles is
better, as in easier to understand, and thus easier to maintain.

Keep in mind that for posting purposes, this is a greatly
simplified example.

The goal is to parse and build an AST for a print statement,
returning the base-node of the AST built.

print ::= "print" expr | string ("," expr | string )*

Given the following AST declaration:

typedef struct Tree {
TreeType type;
struct Tree *next;
union {
...
struct Print {
char *str;
struct Tree *expr;
struct Tree *next;
} Print;
...
};
} Tree;

------------------------------------------------------------
Iterative version - this version closely follows the
specification of the print statement, above. This is the style I
have found in several text-books.

static Tree *parse_print(void) {
Tree *t0, *t;

t = t0 = parse_print_expr(); // first expr
while (tok.sym == commasym) { // more exprs?
t = t->Print.next = parse_print_expr(); // next expr
}
return t0;
}

Supplemental function for above, to save code duplication:

static Tree *parse_print_expr(void) {
Tree *t;

t = newTree(Print);
getsym(); // skip "print" | ","
if (tok.sym == stringsym) {
t->Print.str = strdup(tok.str);
getsym();
} else
t->Print.expr = expr(MINPRIO);
return t;
}

------------------------------------------------------------
Recursive version - I like this version, but since this is C and
not Lisp, will it still be obvious to the maintainer in a year?
Was it a good idea to move the parse_print_expr function inline?

static Tree *parse_print(void) {
Tree *t;

t = newTree(Print);
getsym(); // skip "print" | ","
if (tok.sym == stringsym) {
t->Print.str = strdup(tok.str);
getsym();
} else
t->Print.expr = expr(MINPRIO);
if (tok.sym == commasym) // more exprs?
t->Print.next = parse_print(); // recursive call
return t;
}

------------------------------------------------------------
Iterative version - this version closely models the recursive
version. It seems simple, except for the messy "first-time"
test. Was it a good idea to move the parse_print_expr function
inline?

static Tree *parse_print(void) {
Tree *t0 = NULL, *t;

do {
if (t0) // first time?
t = t->Print.next = newTree(Print); // no, next expr
else
t = t0 = newTree(Print); // else first expr
getsym(); // skip "print" | ","
if (tok.sym == stringsym) {
t->Print.str = strdup(tok.str);
getsym();
} else
t->Print.expr = expr(MINPRIO);
} while (tok.sym == commasym); // more exprs?
return t0;
}

------------------------------------------------------------
Iterative version - this version has the messy 1st "iteration
only" code pulled out of the loop. But, this causes the loop to
terminate in the middle, via a "break". Was it a good idea to
move the parse_print_expr function inline?

static Tree *parse_print(void) {
Tree *t0, *t;

t0 = t = newTree(Print); // first expr
for (;;) {
getsym(); // skip "print" | ","
if (tok.sym == stringsym) {
t->Print.str = strdup(tok.str);
getsym();
} else
t->Print.expr = expr(MINPRIO);
if (tok.sym != commasym) // more exprs?
break; // no, exit loop
t = t->Print.next = newTree(Print); // next expr
}
return t0;
}
Nov 13 '05 #1
Share this Question
Share on Google+
4 Replies


P: n/a
Ed Davis <ed*******@yahoo.com> wrote:
I'm trying to decide which of the following programming styles is
better, as in easier to understand, and thus easier to maintain.


No comment from that perspective.

However, unless I could be certain that the number of recursions will always
be limited (and small), I would go with iterative code -- to avoid possible
stack overflow.

--
Chris Priede (pr****@panix.com)
Nov 13 '05 #2

P: n/a
Ed Davis <ed*******@yahoo.com> wrote:
I'm trying to decide which of the following programming styles is
better, as in easier to understand, and thus easier to maintain. Keep in mind that for posting purposes, this is a greatly
simplified example. The goal is to parse and build an AST for a print statement,
returning the base-node of the AST built. print ::= "print" expr | string ("," expr | string )*


I'm still a newbie to compilers, but it seems to me that you should parse
that as a function call, or procedure call or whatever, and then the
symantec analyzer should insert the appropriate code for the print
function into the IR.

--
Harrison Caudill | .^ www.hypersphere.org
Computer Science & Physics Double Major | | Me*Me=1
Georgia Institute of Technology | '/ I'm just a normal guy
Nov 13 '05 #3

P: n/a
On Thu, 2 Oct 2003 15:15:49 UTC, ed*******@yahoo.com (Ed Davis) wrote:
I'm trying to decide which of the following programming styles is
better, as in easier to understand, and thus easier to maintain.


There is really NO what is better. Often the algorithm you have to use
makes it easier to think in a loop, often the algorithm is clearly
better readable when it is written as recursion.

When you've got some programming praxis you will smell which form is
better.

Whenever you have clearly defined conditions belonging only to exact
the level yo're working on (e.g. a tree) you would go recursive.
Whenever you have side effects you can't control easy (means you don't
know that you have anything well defined you will use some kind of
loop.

--
Tschau/Bye
Herbert

eComStation 1.1 Deutsch wird jetzt ausgeliefert!
Nov 13 '05 #4

P: n/a
ed*******@yahoo.com (Ed Davis) wrote in message news:<42**************************@posting.google. com>...
I'm trying to decide which of the following programming styles is
better, as in easier to understand, and thus easier to maintain.
[...]
------------------------------------------------------------
Iterative version - this version closely follows the
specification of the print statement, above. This is the style I
have found in several text-books.

static Tree *parse_print(void) {
Tree *t0, *t;

t = t0 = parse_print_expr(); // first expr
while (tok.sym == commasym) { // more exprs?
t = t->Print.next = parse_print_expr(); // next expr
}
return t0;
}

Supplemental function for above, to save code duplication:

static Tree *parse_print_expr(void) {
Tree *t;

t = newTree(Print);
getsym(); // skip "print" | ","
if (tok.sym == stringsym) {
t->Print.str = strdup(tok.str);
getsym();
} else
t->Print.expr = expr(MINPRIO);
return t;
}
This is pretty clean, from my point of view.
------------------------------------------------------------
Recursive version - I like this version, but since this is C and
not Lisp, will it still be obvious to the maintainer in a year?
Was it a good idea to move the parse_print_expr function inline?

static Tree *parse_print(void) {
Tree *t;

t = newTree(Print);
getsym(); // skip "print" | ","
if (tok.sym == stringsym) {
t->Print.str = strdup(tok.str);
getsym();
} else
t->Print.expr = expr(MINPRIO);
if (tok.sym == commasym) // more exprs?
t->Print.next = parse_print(); // recursive call
return t;
}


How about:

static Tree *parse_print_r(Tree *T, Tree *t) {

getsym();
if (tok.sym == stringsym) {
t->Print.str = strdup(tok.str);
getsym();
} else {
t->Print.expr = expr(MINPRIO);
}

if (tok.sym != commasym) {
return T;
}

return parse_print_r(T, t->Print.next = newTree(Print));
}

static Tree *parse_print(void) {
Tree *T = newTree(Print);
return parse_print_r(T, T);
}

A decent compiler will now be able to optimize away the recursion
for you.

-- James
Nov 13 '05 #5

This discussion thread is closed

Replies have been disabled for this discussion.