Recursion

  • Thread starter Thread starter Guest
  • Start date Start date
G

Guest

Write a function that produces the same output as MyFunction but without the
use of recursion.
( perfect C# is not a requirement, you may write in pseudo code )
 
This is not a test I just took some samples from book and trying to solve it
.. Please help me.
 
Nevermind. I see your previous post. To do it without recursion, just
figure out what it is really doing. You can do this with a loop.
 
ModelBuilder said:
Nevermind. I see your previous post. To do it without recursion, just
figure out what it is really doing. You can do this with a loop.
Click to expand...

Without giving away one possible solution....I will write this in
descriptive, non pseudo, non actual code :)

I would not use a loop in my own code, rather I would rely on the framework
for doing it for me. You can do this using the Reverse method of the Array
class, after converting the string to a character array, then pass the
results of the Reverse method to the constructor of the string class.
Voila, results!

:)

HTH,
Mythran
 
According to my textbook on Pascal, written by Robert L. Kruse, any
recussive problem can (and should) be made into a more efficient non-
recursive problem.

The solution is to employ a stack, do stuff you need to do in a loop,
then pop off the stack stuff that you put off. It's straightforward,
once you get used to it. In fact I find recursion harder to understand
than a loop.

In fact I'm writing code for traversing an N-ary tree non-recursively
right now.

Just put your mind to it.

RL
 
raylopez99 said:
According to my textbook on Pascal, written by Robert L. Kruse, any
recussive problem can (and should) be made into a more efficient non-
recursive problem.

The solution is to employ a stack, do stuff you need to do in a loop,
then pop off the stack stuff that you put off. It's straightforward,
once you get used to it. In fact I find recursion harder to understand
than a loop.
Click to expand...

If you refactor a recursive algorithm so that it uses an explicit stack,
it's still essentially recursive.

Many algorithms implemented recursively can in fact be implemented
iteratively, _and_ without using a stack. Tail recursion is the
classic, obvious example. But if all you're doing is moving the stack
from the compiler-generated code to your own code, then you've done
little else but to obfuscate the underlying algorithm and create more
work for yourself, without changing the basic recursive nature of the
algorithm.

Pete
 
Okay. (BTW, it would correctly be referred to as MyMethod):

public static MyMethod MyMethod(MyMethod myMethod)
{
return myMethod;
}

Works for me, friend! Garbage in, garbage out....
 
seema said:
Write a function that produces the same output as MyFunction but without the
use of recursion.
( perfect C# is not a requirement, you may write in pseudo code )
Click to expand...

Hint: look at string.ToCharArray() and Array.Reverse().
 
-----Original Message-----
From: raylopez99 [mailto:[email protected]]
Posted At: Tuesday, 14 August 2007 8:30 AM
Posted To: microsoft.public.dotnet.languages.csharp
Conversation: Recursion
Subject: Re: Recursion

According to my textbook on Pascal, written by Robert L. Kruse, any
recussive problem can (and should) be made into a more efficient non-
recursive problem.

The solution is to employ a stack, do stuff you need to do in a loop,
then pop off the stack stuff that you put off. It's straightforward,
once you get used to it. In fact I find recursion harder to understand
than a loop.

In fact I'm writing code for traversing an N-ary tree non-recursively
right now.

Just put your mind to it.
Click to expand...

I reckon that a good example of recusion is writing a function that
processes an include directive in a file and that the include files can
contain includes.

Parsing directory structures and trees also lend themselves naturally to
recursion.

(The example often used of factorials doesn't).
 
I reckon that a good example of recusion is writing a function that
processes an include directive in a file and that the include files can
contain includes.

Parsing directory structures and trees also lend themselves naturally to
recursion.

(The example often used of factorials doesn't).
Click to expand...

Hi,

Back in my univ days I was taugh recursion using Hanoi towers :)
 
raylopez99wrote:
Click to expand...
Many algorithms implemented recursively can in fact be implemented
iteratively, _and_ without using a stack. Tail recursion is the
classic, obvious example.
Click to expand...

And many cannot I suppose? :-)

I was thinking--and so far with my N-ary tree it seems to be working--
of storing the 'state variables' of the algorithm (in my case the
nodes that are next to go through the iterative loop)--on the stack.
So you're not really wasting memory, since these nodes are tiny, nor
are you replicating the itteration, insofar as I can tell. And I
can't figure out any other way of traversing and/or building the N-ary
tree, without adding pointers within the nodes, which, come to think
of it, is not a bad idea (though storing pointers within the nodes
also is a cost, in terms of extra memory used by each node), but not
the way I'm proceeding at the moment.

RL
 
raylopez99 said:
And many cannot I suppose? :-)
Click to expand...

Well, any algorithm that requires storing previous state all the way
back to the original root case is going to have to use some kind of
stack-like data structure.

The fact is, even here there are ways to change the problem so that a
stack isn't required. For example, you can do an in-order traversal of
a tree without a stack as long as the child nodes refer back to the
parent. One implementation I've seen just keeps a "next in-order node"
reference, so all the children except the last point to their sibling,
with that last sibling pointing back to the parent.

But in that situation, you've taken a tree data structure and overlaid a
plain list onto it. I would argue that you haven't so much implemented
a recursive algorithm without a stack, so much as simply changed the
data structure so that it's no longer a recursive algorithm to enumerate
the data structure.
I was thinking--and so far with my N-ary tree it seems to be working--
of storing the 'state variables' of the algorithm (in my case the
nodes that are next to go through the iterative loop)--on the stack.
So you're not really wasting memory, since these nodes are tiny, nor
are you replicating the itteration, insofar as I can tell.
Click to expand...

On which stack? The actual call stack? Or an explicit data structure
of your own making? Either way, the algorithm is still recursive. The
difference is that if you create an explicit data structure, now you
have to write all the code to maintain it as well. If you just use the
call stack, your code is not cluttered with details not directly
relating to the algorithm itself.
And I
can't figure out any other way of traversing and/or building the N-ary
tree, without adding pointers within the nodes, which, come to think
of it, is not a bad idea (though storing pointers within the nodes
also is a cost, in terms of extra memory used by each node), but not
the way I'm proceeding at the moment.
Click to expand...

That solution is basically the same as what I mention above. But then
you are simply adding a new data structure -- a list -- to your existing
one.

It's not a bad solution, but really...there's nothing wrong with
recursion per se. In a situation where recursion is the clearest,
simplest code to write, you ought to just go ahead and use it. And
there's no reason to implement your own stack; C# has a perfectly good
automatically-maintained stack of its own that you can take advantage of.

That's not to say that there's no need for an alternative stack
structure. Any time that the maintenance of the stack does not itself
correspond exactly to the flow of the code, you need to keep one that is
separate from the regular call stack. But for something like this,
that's not the case.

Pete
 
Back
Top