473,320 Members | 1,831 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

is there problem that "has to" use recursion

Hi

Please give problems that "HAS TO" to use recursion (recursive calls to
itself.)
Preferrably real world examples, not knights tour.

I'm thinking about eliminating the use of stack...

Thanks.

Nov 14 '05 #1
10 2473
[F'ups set to comp.programming]

p...@mmail.ath.cx wrote:

Please give problems that "HAS TO" to use recursion (recursive
calls to itself.)


This is not a C language question and, as such, it is off-topic
in clc.

The C language does provide recursion, for those who want to use
it. However, it is subject to practical and pragmatic caveats that
are also largely off topic in clc since the C language standards
provide no minimal implementation requirements on either depth or
efficieny of recursion.

--
Peter

Nov 14 '05 #2
pa***@mmail.ath.cx wrote:

Please give problems that "HAS TO" to use recursion (recursive
calls to itself.) Preferrably real world examples, not knights tour.

I'm thinking about eliminating the use of stack...


Can't. There are known standard means of eliminating recursion,
which may involve the use of an auxiliary stack. Since this can
always be done, no problem actually relies on recursion.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

Nov 14 '05 #3
pa***@mmail.ath.cx wrote:
Please give problems that "HAS TO" to use recursion (recursive calls to
itself.) Preferrably real world examples, not knights tour.

I'm thinking about eliminating the use of stack...


None, if you're merely thinking about eliminating the use of the call
stack; you can always flatten the algorithm into an iterative one,
possibly with the use of your own stack ADT. Many, if you mean
eliminating any stack at all; quicksort, for example, uses recursion on
both halves of the array, and AFAIK only the second half can be
eliminated without the use of a hand-written stack.

Richard
Nov 14 '05 #4
<pa***@mmail.ath.cx> wrote:
Please give problems that "HAS TO" to use recursion (recursive calls to
itself.)
Preferrably real world examples, not knights tour.

I'm thinking about eliminating the use of stack...


The first paragraph is theoretical (as used in ordinary conversation) and
the second is practical. I suggest rephrasing the first paragraph and ask
"What is an example of a problem where it would be impractical to use an
iterative solution?" This will, of course, open a discussion on the meaning
of "impractical" by the purists. But you might by chance get a meaningful or
useful answer too, mixed in with all the noise. But this is the wrong group
too, try going "up a notch". programming, compiling, math, ....
Nov 14 '05 #5
jxh
pa***@mmail.ath.cx wrote:
Please give problems that "HAS TO" to use recursion (recursive
calls to itself.)
Preferrably real world examples, not knights tour.
Implementing a sort in scheme. Well, implementing anything in
scheme that involves iterating an indeterminate number of
times.

Defining a grammar in BNF for a regular language that contains
strings of indeterminate size.

Proving Goedel's Theorem.

What was your C question?
I'm thinking about eliminating the use of stack...


Well C doesn't really define a stack. You can define functions,
and you can call functions. Inside a function, you can define
automatic variables. Functions can be defined to take arguments
which are treated like automatic variables that are initialized
by the caller of the function. C supports recursion in that the
caller can call any function whose name is in scope.

So if we replace "stack" with "function call", then you have old
style BASIC.

-- James

Nov 14 '05 #6
pa***@mmail.ath.cx wrote:
...
Please give problems that "HAS TO" to use recursion (recursive calls to
itself.)
Preferrably real world examples, not knights tour.

I'm thinking about eliminating the use of stack...
...


The answer depends heavily on what you mean under "recursion". A
syntactic recursion (when one function in a program calls itself
directly or indirectly) is very easy to eliminate in all cases.

The algorithmic recursion (if defined as a LIFO-based application of
Divide&Conquer approach) cannot be eliminated in general case. A simple
real-world example is a depth-first tree traversal of a tree that only
has parent->child links, but no child->parent links (assuming that the
input tree is non-modifiable and that the required complexity is O(n),
where 'n' is the number of nodes).

Informally speaking, if the input data structure is inherently and
essentially recursive, the processing algorithms will always be
recursive and there's no way around it. The implementations of these
algorithms, of course, will not necessarily employ syntactic recursion.

--
Best regards,
Andrey Tarasevich
Nov 14 '05 #7
pa***@mmail.ath.cx wrote:
Please give problems that [must] use recursion
(recursive calls to itself.)
Since there are none,
I have given all of them.
Preferrably real world examples, not knights tour.

I'm thinking about eliminating the use of stack.


Why? Recursion is your friend.
A good optimizing C compiler can convert a recursive function
into the equivalent iterative function automatically
if there is indeed any advantage to doing so.

I used Google

http://www.google.com/

to search for

+"tail-recursion optimization" +"C program"

and I found lots of stuff.
Nov 14 '05 #8
In article <11**********************@z14g2000cwz.googlegroups .com>,
jxh <jx*@despammed.com> wrote:
pa***@mmail.ath.cx wrote:
Please give problems that "HAS TO" to use recursion (recursive
calls to itself.)
Defining a grammar in BNF for a regular language that contains
strings of indeterminate size.


<word> ::= <letter> | <letter> <word>

That does not use recursion at the -syntatic- level, and it does not
*need* recursion in order to do semantic analysis of a potential word.
At the semantic analysis level, it becomes just a simple regular
expression, processable by a DFA (Deterministic Finite Automata) with
nothing more than a "current state" variable if you are just trying to
recognize <word>.
:Proving Goedel's Theorem.

Which of Goedel's Theorem's? His Completeness Theorem? His
Incompleteness Theorem? There is a particular point in the usual
proof of the Incompleteness Theorem in which a number representing
a function with one free variable is applied to itself in order to
go from the step "Some statements are false" to "This particular
statement is false", but in one case the number is being
"used" and in the other case the number is being "mentioned",
with there being no location that I can recall in the theorem
proof in which a number is used upon itself multiple times --
no recursion, just a simple one-step evaluation.
There is no finitely computable result which cannot be represented
as a Turing Machine; Turing Machines have no "recursion" as we
commonly think of it (but they do have a stack of indefinite length.)
Every finite recursive function programmable in C has a maximum
number of calls, N, which can be simultaneously logically active; e..g,

g(x-1) * g(x+1) - g(x+1) * g(x-1)

has 4 in that fragment. This can be converted into an interative
structure which uses an indefinitely-sized block of memory each
element of which is
N by the size of the returned value
plus 1 times the size of the argument
plus something large enough to hold 0 .. N to indicate what has
been finished

A linked list of structures could be used to hold this.

Once this is in place, the code can proceed iteratively: the top
element of the stack / linked list / "work list" tells you which
value has to be processed next by looking at the counter,
and the value slots are used to save intermediate results.
What is the difference between this and calling the function
recursively? Not much, really -- automatic stack storage
by repeated calling, plus the return PC automatically stored
on the stack are equivilent to the above storage structure
and a linked list. But when the question arises as to
what *must* be done recursively, this transformation can
be trotted out to show that there is no finitely computable
result which is programmable in C that *must* be programmed
with recursion.
--
'The short version of what Walter said is "You have asked a question
which has no useful answer, please reconsider the nature of the
problem you wish to solve".' -- Tony Mantler
Nov 14 '05 #9
"E. Robert Tisdale" <E.**************@jpl.nasa.gov> writes:
pa***@mmail.ath.cx wrote:
Please give problems that [must] use recursion
(recursive calls to itself.)


Since there are none,
I have given all of them.
Preferrably real world examples, not knights tour.
I'm thinking about eliminating the use of stack.


Why? Recursion is your friend.
A good optimizing C compiler can convert a recursive function
into the equivalent iterative function automatically
if there is indeed any advantage to doing so.

I used Google

http://www.google.com/

to search for

+"tail-recursion optimization" +"C program"

and I found lots of stuff.


Sure, but tail-recursion optimization doesn't cover all cases of
recursion.

Tail-recursive functions are particularly easy to convert to iterative
functions, but all recursive functions can be converted to an
iterative form (possibly with the use of an explicit stack).

Doing so might make sense on a small embedded system that might limit
the depth of the call stack, or where avoiding the overhead of nested
function calls can be worthwhile.

In most cases, though, if a problem is inherently recursive, recursion
is the best way to implement the solution.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 14 '05 #10
jxh
Walter Roberson wrote:
In article <11**********************@z14g2000cwz.googlegroups .com>,
jxh <jx*@despammed.com> wrote:
pa***@mmail.ath.cx wrote:
Please give problems that "HAS TO" to use recursion (recursive
calls to itself.)
Defining a grammar in BNF for a regular language that contains
strings of indeterminate size.


<word> ::= <letter> | <letter> <word>

That does not use recursion at the -syntatic- level,
...


Err... the recursion is in defining <word> in terms of <word>.

I said: "Defining a grammar..."
:Proving Goedel's Theorem.

... There is a particular point in the usual
proof of the Incompleteness Theorem in which a number representing
a function with one free variable is applied to itself in order to
go from the step "Some statements are false" to "This particular
statement is false",
...


The recursion is in why it is not possible to prove the true
statement.

.... snip ...

Since the question was not a C question to begin with, and since
the original poster did not limit his question to programming
problems, I did not limit my answer to such. YMMV.

My full answer already noted the C constructs that would have to
be eliminated to get the effect of eliminating a "stack" in the
sense that I believe the original poster meant.

-- James

Nov 14 '05 #11

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

Similar topics

16
by: Maciej Kalisiak | last post by:
I use this simple test in Python: def foo(i): print i foo(i+1) import sys sys.setrecursionlimit(1000000) foo(0) Now, my understanding is that I get the segfault when Python overruns the C
12
by: Mikito Harakiri | last post by:
I wonder if WITH RECURSIVE MaryAncestor(anc,desc) AS ( (SELECT parent as anc, child as desc FROM ParentOf WHERE desc = "Mary") UNION (SELECT A1.anc, A2.desc FROM MaryAncestor A1, MaryAncestor...
40
by: aku | last post by:
I'm looking for the absolute fastest way to count the nr of bits that are set to "1" in a string. Presumably I then first need the fastest way to do this in a byte. I think this is it, but...
3
by: kiplring | last post by:
Suppose a function which has Sleep() method in it. And I want to recycle it. I made two buttons which call "Resume()" and "Suspend()". But It doesn't work. The state of thread "t" will be...
71
by: Greg | last post by:
Is it your general opinion that C# is generally designed/intended/ready to replace C++? I know the answer is not black and white but please repond YES or NO (add any comments if you would like) ...
2
by: Leo | last post by:
Dear All, Can I do this: class MyClass() { public: doStuff(); private: int iNum;
10
by: Angel | last post by:
I have the following code var thisDoc=document.getElementById("myTable"); // myTable is the name of the table alert(thisDoc.childNodes.children.length) How do I change the second line of code...
2
by: rakesh kumawat | last post by:
I am facing a problem while reading the result which is loaded in DOMDocument. In which I am sending a request to web service and getting a record of Single Order. This is my VB Code which is i am...
1
by: Mateusz | last post by:
Hello, I new on this forum :-) I've got some problem with my script. I'm writing some script, when FF say "document.forms.google_bot has no properties" look at this code : <script...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

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.