Below is a sample walker that will make this idea clear. When invoked on every unitNode, the Walker traverses the AST, listing all the recursive functions in the program.
class recursionWalker: public Walker {
private:
string current_proc_name; // name of the current proc
bool is_recursive; // the current proc is recursive
public:
// The constructor calls the constructor for Walker, indicating that
// we'll be descending subtrees in both preorder and postorder.
recursionWalker (void): Walker (Both, Subtree) {};
// What to do at a function definition
void at_proc (procNode *p, Order ord) {
// get the declaration for the function
declNode *d = p->decl();
// What order are we visiting this node from?
if (ord == Preorder) {
// If we haven't visited the function body yet, simply
// remember the current procedure's name and initialize
// is_recursive to false
current_proc_name = d->name();
is_recursive = false;
} else {
// After we're done with the function body, print a
// message if this function was determined to call
// itself
if (is_recursive)
cout << d->name() << " is recursive\n";
}
}
// what to do at a function call (sub)expression
void at_call (callNode *c, Order ord) {
// If the 'name' (really the expression by which the function
// is called) is an identifier expression whose name is the
// same as that of the current function, the function is
// recursive. If we're not visiting in Preorder, then we're
// done, so we'll avoid needlessly executing the 'if' body
// again.
if (ord == Preorder && c->name()->typ() == Id) {
idNode *i = (idNode *) c->name();
if (i->name() == current_proc_name)
is_recursive = true;
}
}
};