is there problem that "has to" use recursion

[paulw]

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.

 

[Peter Nilsson]

[F'ups set to comp.programming]

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.

 

[CBFalconer]

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.

 

[Richard Bos]

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

 

[osmium]

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

 

[jxh]

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

 

[Andrey Tarasevich]

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

 

[E. Robert Tisdale]

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.

 

[Walter Roberson]

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


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

 

[Keith Thompson]

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.

 

[jxh]

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

roving 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