473,558 Members | 2,827 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

detect recursive C code

Hi all,

is there a good way to detect recursive C code in large systems? A
method or a free tool?

Best regards,
E
Nov 14 '05 #1
6 4526
In article <68************ **************@ posting.google. com>,
Einar ?rn <or******@yahoo .se> wrote:
is there a good way to detect recursive C code in large systems? A
method or a free tool?


I don't know of anything specifically for that purpose, but many
profilers indicate recursive cycles in their output. This will only
detect recursive functions that are actually called of course.

-- Richard
Nov 14 '05 #2
On 28 Oct 2004 07:22:53 -0700, or******@yahoo. se (Einar ?rn) wrote:
Hi all,

is there a good way to detect recursive C code in large systems? A
method or a free tool?

Best regards,
E


I don't know if it meets the exact purpose, but I think GLOBAL is a
suitable tool to reverse engineer C source code and caller/callee
dependencies (http://www.gnu.org/software/global). You can of course
try doxygen (http://www.doxygen.org), it can create call-trees and
therefore should find recursions (although I never tried that)

Mark

Nov 14 '05 #3

In article <68************ **************@ posting.google. com>, or******@yahoo. se (Einar ?rn) writes:

is there a good way to detect recursive C code in large systems? A
method or a free tool?


There are a number of static-analysis tools that generate call graphs
from C source. Loops in the call graph indicate recursion. They're
not guaranteed, though:

- If the recursion only occurs in dead code which is never actually
executed, you may have a false positive (depending on how you define
"recursive C code" for your purposes).

- It's hard for analyzers to detect recursion through function
pointers, since they'd have to check every value such a pointer can
be set to by the program; so if the code uses function pointers you
could get false negatives.

Dynamic (runtime) analysis obviously suffers from flow coverage
issues - you can't rule out recursion until you've tested all
possible flow paths through the code.

In short, it's very difficult (maybe impossible, though I don't
offhand see a proof of that; this doesn't look to me like it's
isomorphic to the halting problem) to algorithmically determine that
a given body of C code is not recursive.

A program could detect recursion at runtime (given sufficient
resources) by maintaining its own stack of tokens identifying which
functions have been called in the current path; each function on
entry checks the stack to see if it's already there, and then adds
itself to the top. The repetitive code can be hidden in macros, but
this is still not particularly fun to implement. And, of course, you
have to decide what the program does if it detects recursion.

--
Michael Wojcik mi************@ microfocus.com

When most of what you do is a bit of a fraud, the word "profession "
starts to look like the Berlin Wall. -- Tawada Yoko (t. M. Mitsutani)
Nov 14 '05 #4
mw*****@newsguy .com (Michael Wojcik) wrote in message news:<cl******* **@news4.newsgu y.com>...
(...) this doesn't look to me like it's
isomorphic to the halting problem) to algorithmically determine that
a given body of C code is not recursive.

Actually, it is. Informally, you need to determine that the program
can reach another particular point in the code (which is trivially
equivalent to the halting problem), given a particular starting point
before reaching another point (eg. the next line), which is an
additional complication.

A program could detect recursion at runtime (given sufficient
resources) by maintaining its own stack of tokens identifying which
functions have been called in the current path; each function on
entry checks the stack to see if it's already there, and then adds
itself to the top. The repetitive code can be hidden in macros, but
this is still not particularly fun to implement. And, of course, you
have to decide what the program does if it detects recursion.

While quite implementation dependant (and using very undefined
behavior), if you can, on your implementation, walk the stack of
activation records, it's usually pretty easy to write a routine that
saves the callers address in an auto, and then looks through all the
stack frames looking for a duplicate. All you need in each routine is
something like "{void *RecurseTest; CheckRecursion( &RecurseTest ,
__LINE__);}"
Nov 14 '05 #5
> dependencies (http://www.gnu.org/software/global). You can of course
try doxygen (http://www.doxygen.org), it can create call-trees and


Thanks for the answers, however I never found out how to use these
tools so I used the excelent tool cflow instead.

http://www.opengroup.org/onlinepubs/...ies/cflow.html

It prints a callgraph and marks the recursive functions.
E.
Nov 14 '05 #6
On 29 Oct 2004 15:48:59 GMT, mw*****@newsguy .com (Michael Wojcik)
wrote:
<snip>
A program could detect recursion at runtime (given sufficient
resources) by maintaining its own stack of tokens identifying which
functions have been called in the current path; each function on
entry checks the stack to see if it's already there, and then adds
itself to the top. The repetitive code can be hidden in macros, but
this is still not particularly fun to implement. And, of course, you
have to decide what the program does if it detects recursion.


Or a static flag, (as little as) one bit, for each function.

With somewhat simpler code; but still worth hiding, and also
automating which helps prevent cut&paste or other editing errors.
- David.Thompson1 at worldnet.att.ne t
Nov 14 '05 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

1
13512
by: Mat | last post by:
How can I detect when a link has been clicked but the new page is still in the process of loading? The document.location.href property still displays the current location (understandably) not the one that's about to load. I have a page that reloads every 30 seconds in order to access live data. If a user clicks on a link just prior to the...
7
567
by: Jon Slaughter | last post by:
#pragma once #include <vector> class empty_class { }; template <int _I, int _J, class _element, class _property> class RDES_T {
1
2373
by: Jon Slaughter | last post by:
I've managed to put together a template class that basicaly creates a recursive tree that lets you easily specify the "base" class of that tree and and ending notes and lets you stop the recursive process if you want. The problem now is to make a Type list so I can specify more than one node at a time to "attach" a class to. I think I will...
4
2420
by: Nicolas Vigier | last post by:
Hello, I have in my python script a function that look like this : def my_function(arg1, arg2, opt1=0, opt2=1, opt3=42): if type(arg1) is ListType: for a in arg1: my_function(a, arg2, opt1=opt1, opt2=opt2, opt3=opt3) return if type(arg2) is ListType:
0
299
by: Einar ?rn | last post by:
Hi all, is there a good way to detect recursive C code in large systems? A method or a free tool? Best regards, E
0
1950
by: champ1979 | last post by:
I wrote an algorithm to get all the relatives of a person in a family tree. I'm basically getting all the users from the DB and am doing the recursive logic in code, so that there is only 1 call made to the DB. However, I am trying to do the same thing within a stored procedure in SQL using recursive CTEs (I think the performance might be better)...
18
4698
by: Just Another Victim of the Ambient Morality | last post by:
Is pyparsing really a recursive descent parser? I ask this because there are grammars it can't parse that my recursive descent parser would parse, should I have written one. For instance: from pyparsing import * grammar = OneOrMore(Word(alphas)) + Literal('end') grammar.parseString('First Second Third end')
4
2116
by: ThEoNeAnDOnLy | last post by:
I recently had an issue with my recursive project in class. Here is the code. // Recursion.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <conio.h> #include <iostream> using namespace std;
3
4221
by: from.future.import | last post by:
Hi, I encountered garbage collection behaviour that I didn't expect when using a recursive function inside another function: the definition of the inner function seems to contain a circular reference, which means it is only collected by the mark-and-sweep collector, not by reference counting. Here is some code that demonstrates it: ===...
0
7629
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
0
7549
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
0
7835
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. ...
0
8061
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
1
7593
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
0
6183
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
1
5455
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
1
1164
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
0
869
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.