Recursion Usage and Concepts - Newbie Question

[Taria]

Hello all,

I'm struggling with an assignment that involves using a 'quicksort'
search for a user defined kth element within a list of numbers. The
use of recursion is a requirement of this assignment.

From what I understand, recursion breaks down a big task into smaller

tasks until it solves the problem. My question is this: (I hope I
make sense in asking this) what if I was only interested in the result
at the very end of the recursion, how would I pass that value I found
to the first calling statement?

I figured out (and I'm sure my program is clumsy) how to recusively
solve the assignment but I don't know how to pass back the value I
find (after I split the list into smaller bits.) I could put a print
statement right there to indicate my answer, but after looking at a
few examples of other ppl's recursive Java routines, I feel
uncomfortable with this solution. I feel like I should be able to pass
back a value at the end of a recusrive call without it being changed
when it's returning to the main routine (yes, that's what happened
i.e. I HAD a statement that looked similiar to this:

return (aValue);

and it changed the value of aValue to something else. Conceptually,
should I be able to use that statemen above?

Also, because I'm so intimidated by the idea of recursion and still
somewhat afraid of objects, I resorted to using static methods instead
of objects. Am I hurting myself by doing this? Isn't the concepts of
the behavior of recursion the same whether it be by object or static?
All the examples I'm looking at use objects hence I've begun to
question my pursuit of using static methods. (Really, I was going
to rewrite this program using object-oriented code after I figured out
the recursive part, I know I can do it! )

Any advice is appreciated and I apologize in advance for anything that
sounds 'wrong.'

-t

 

[Roedy Green]

I'm struggling with an assignment that involves using a 'quicksort'
search for a user defined kth element within a list of numbers. The
use of recursion is a requirement of this assignment.

You can have a look at an working Quicksort by downloading
http://mindprod.com/products.html#QUICKSORT

 

[Roedy Green]

Also, because I'm so intimidated by the idea of recursion and still
somewhat afraid of objects,

see http://mindprod.com/jgloss/recursion.html

You might write something simple to get over your fear. The key thing
to understand is each layer of call has its own local variables. When
you return, it remembers everything as they were before you did the
call.

 

[Eric Sosman]

Hello all,

I'm struggling with an assignment that involves using a 'quicksort'
search for a user defined kth element within a list of numbers. The
use of recursion is a requirement of this assignment.

From what I understand, recursion breaks down a big task into smaller

tasks until it solves the problem. My question is this: (I hope I
make sense in asking this) what if I was only interested in the result
at the very end of the recursion, how would I pass that value I found
to the first calling statement?
[...]

The usual way to apply recursion is to divide a maxi-problem
into two or more mini-problems, solve the minis, and combine
their solutions to find the answer to the maxi-problem. The
"recursive" aspect means that you apply the same technique to
solve the mini-problems: Split them into micro-problems, solve
the micros, and combine their solutions to solve the minis.
And the micro-problems split into nano-problems, and so on.
As the levels descend you eventually arrive at problems that
are so small they can be solved by some other means (this is
sometimes called the "ground case").

The magic piece I think you may be missing is that each
small problem's solution is passed back to the recursive step
that asked for it, where it gets combined with the solutions
of other small problems to solve the larger problem. I don't
much blame you for this, because the assignment you've been
told to solve recursively isn't really suited to recursion:
most of the split-and-recombine steps are degenerate, vacuous,
and easy to overlook.

But let's look at the structure anyhow. You rearrange
the original list of numbers into sub-lists, and learn that
one of those sub-lists holds the number you want (you don't
know where it is in that sub-list, but you know it's there).
The *other* sub-lists are "solved" trivially: They don't
hold the number of interest, so you're finished with them.
Their "solutions," if you like, are empty.

The "hot" list still needs to be solved, though, so you
can call your own method to get a solution for it. (It's
best at this point to pretend that this second-level call
just works by magic or something; we'll get to the details
later.) The inner call returns its answer, which you "combine"
with the answers from the other sub-lists (by ignoring them;
you already know they don't matter), so the answer returned
by the inner call is also the answer you return.

Now to the magic piece. The outer call was asked to find
the Kth-largest of a big list, and the inner method is told
to find the Lth-largest of a smaller list. If the small list
is *really* small -- one number, for example -- you can find
the solution easily and return it. If it's longer you can
apply the same technique the outer call did: divide the short
list into still shorter lists, ignore most of them, and call
yourself yet again to find the Mth-largest of the one interesting
very short list.

As I said, it's not the best example for illustrating the
recursive technique. At each stage you ignore all but one of
them sub-problems (usually you would need to solve them, too),
and the combine-the-answers step is trivial (usually you need
to do a little more computing at this point).

Here's a better one: Imagine adding a million numbers with
pencil and paper. It'd take forever, but fortunately you have
a hundred friends: You give each of them ten thousand of the
numbers and ask for the sub-totals, then you add the hundred
sub-totals to get the grand total. Clear?

Here's the recursive bit: The hundred friends don't want
to add ten thousand numbers apiece, but luckily each of them
has another hundred friends. So they divide their batches of
ten thousand into a hundred batches of a hundred and dole those
out to *their* friends. Each friend-of-a-friend adds his group
of a hundred numbers (the "ground case"), then they pass their
totals to one of your friends. Your friends add up their
hundred sub-sub-totals and pass them back to you, and you (as
we said before) add them to get the grand total.

And that's recursion: Divide into sub-problems, solve
sub-problems recursively or directly, combine the solutions,
and report the result to the caller.

 

[Lew]

No.

The usual way to apply recursion is to divide a maxi-problem
into two or more mini-problems, solve the minis, and combine
their solutions to find the answer to the maxi-problem.

No.

Recursion refers to a routine that calls itself, as with the classic Fibonacci
sequence method:

public static int fibonacci( int n )
{
if ( n < 0 ) return 0;
if ( n == 0 || n == 1 )
{
return 1;
}
return fibonacci( n - 1 ) + fibonacci( n - 2 );
}

Notice that fibonacci() calls itself, unless certain conditions are met. If
those conditions didn't exist, the recursion would never end.

If the routine doesn't call itself, you will not get a good grade on the
assignment.

Try looking up "Recursion (computer science)" in Wikipedia.

 

[Jean-Baptiste Nizet]

You could combine the explanations from Eric and Lew with this
problem:

Count the number of files in a directory tree.

The problem is easily solved using recursion. Here's the structure of
the code

int countFilesInTreeWithRoot(File directory) {
int numberOfFilesInTheDirectory = countFilesInDirectory(directory);
int result = numberOfFilesInTheDirectory;
File[] subDirectories = getSubDirectories(directory);
for (File subDirectory : subDirectories) {
result += countFilesInTreeWithRoot(subDirectory);
}
return result;
}

The ground cases here are the "leaf" directories, i.e. directories
which don't have any subdirectory. In this case, the answer of the
problem is trivial: the tree is reduced to the directory itself, and
the answer is the number of files it contains.
For a non-leaf directory, the result is the number of files directly
stored under this directory + the number of files found recursively in
each of its subDirectories.

You end up with the above method, which calls itself recursively,
unless the directory given as argument is a lead directory.

JB.

JB.

 

[Lew]

int countFilesInTreeWithRoot(File directory) {
int numberOfFilesInTheDirectory = countFilesInDirectory(directory);
int result = numberOfFilesInTheDirectory;

Why do you feel that you need two variables for the same value?

File[] subDirectories = getSubDirectories(directory);
for (File subDirectory : subDirectories) {
result += countFilesInTreeWithRoot(subDirectory);
}
return result;
}

int countFilesInTreeWithRoot(File directory) {
int result = countFilesInDirectory(directory);
File[] subDirectories = getSubDirectories(directory);
for (File subDirectory : subDirectories) {
result += countFilesInTreeWithRoot(subDirectory);
}
return result;
}

 

[Taria]

No.



No.

Recursion refers to a routine that calls itself, as with the classic Fibonacci
sequence method:

public static int fibonacci( int n )
{
if ( n < 0 ) return 0;
if ( n == 0 || n == 1 )
{
return 1;
}
return fibonacci( n - 1 ) + fibonacci( n - 2 );

}

Notice that fibonacci() calls itself, unless certain conditions are met. If
those conditions didn't exist, the recursion would never end.

If the routine doesn't call itself, you will not get a good grade on the
assignment.

Try looking up "Recursion (computer science)" in Wikipedia.

Wow, don't you guys sleep? It's 4am here!

Ok, well, I figured out how to make the recursive routine I wrote
perform the way I wanted it to (yay!) and the form sort of looks like
what was posted above.

And I have only one more question about the definition of recursion.

Given the fibonacci recursion routine above, let's say I were to have
a more complex method where I have to determine certain variables (the
parameters) before calling it again...is that considered recursion?
For example in psuedocode and Java:

public static int myMethod (int parm1, int parm2, int parm3){

//if (the parms don't give me what I'm looking for)
//then keep on searching the list

//arbitrary data manipulation here
//the parms shrink in length as they are called over and over.
int parm4 = parm3 - parm1;
int parm5 = parm2 - 1;

if (someVar1 > someVar2) {
aResult = myMethod (parm1, parm5, parm4);
}
else {
if someVar2 > someVar1) {
aRssult = myMethod (parm1, parm4, parm3);
}
slse {
//I found my value here!
return (happyValue); //this would be the base case
}
{
return (aResult)

The meaning of why I'm changing the values of the parms is not
important, but I'm calling myMethod again inside itself. Is that the
same concept of recursion as shown in the Fibonacci recursion
routine? It's certainly not as pretty but it feels right but that
doesn't say much.

The example code above is conceptually what I wrote for this
assignment. The 2 returns listed in it bothers me but it wouldn't
compile unless I put a return at the very bottom (outside of all the
if's, while and what have you statements.)

I've been advised by more than one professor not to use Wikipedia as a
resource! I still go to it though, it's everywhere and lots of
info. I thank all of you for your help.

-t

One thing good about insomnia is that you can spend time coding
recursion Java programs.

 

[Taria]

Sometimes I wish they had delete msg here! I just discovered that you
can put the name of a method in your return statement! Wow!! It looks
better, works the same, makes more sense, too!

(Thanks to the Fibonacci example code ... I noticed somethng on it
that I didn't before.)

Does it matter how many returns you have in your recursion method? Is
it ok to have 3 returns in it? Like if I want it to sort just the
right side of the array, I call it again with right side array values,
vice versa for left and base case has its own return too.

And I hope you guys realize that the directory code was a bit
overwhelming for me right now. I see what you are trying to show.

thanks again!
-t

Now onward to trying to implement this with object oriented code.

 

[Jean-Baptiste Nizet]

Why do you feel that you need two variables for the same value?

Err, I don't know. You're right. It's stupid.

 

[Jean-Baptiste Nizet]

Sometimes I wish they had delete msg here! I just discovered that you
can put the name of a method in your return statement! Wow!! It looks
better, works the same, makes more sense, too!

(Thanks to the Fibonacci example code ... I noticed somethng on it
that I didn't before.)

Does it matter how many returns you have in your recursion method? Is
it ok to have 3 returns in it? Like if I want it to sort just the
right side of the array, I call it again with right side array values,
vice versa for left and base case has its own return too.

You probably don't realize it, but you could start a religious war by
asking such a question

It's a matter of taste, readability and maintainability. Some people
don't like multiple return statements at all in a method. One of the
often heard arguments is that having only one return statement helps
in debugging: you just put a log and/or breakpoint just before the
unique return statement to know what the method returns.
On the other hand, it's sometimes easier to read and follow when you
have several return statements, and it helps avoiding too many
statement imbrications. For example code like

public String foo(String s) {
if (s == null) {
return null;
}

// some complex code
}

is easier to read (usually) than

public String foo(String s) {
String result;
if (s == null) {
result = null;
}
else {
// some complex code
}
return result;
}

And I hope you guys realize that the directory code was a bit
overwhelming for me right now. I see what you are trying to show.

Sorry. I wanted to give you this example because I consider it more
concrete, though a bit more complex, than the traditional fibonacci
example.
If the fibonacci example is sufficient for you to understand the
concept, then fine.

JB.

 

[Eric Sosman]

Lew wrote On 10/12/07 09:04,:

No.




No.

You've misspelled "Yes."

Recursion refers to a routine that calls itself, as with the classic Fibonacci
sequence method:

public static int fibonacci( int n )
{
if ( n < 0 ) return 0;
if ( n == 0 || n == 1 )
{
return 1;
}
return fibonacci( n - 1 ) + fibonacci( n - 2 );
}

Notice that fibonacci() calls itself, unless certain conditions are met. If
those conditions didn't exist, the recursion would never end.

Notice also that the function does exactly as I
described: It decomposes the maxi-problem of finding
fibonacci(n) into the mini-problems of fibonacci(n-1)
and fibonacci(n-2), then it combines the solutions of
those smaller problems to reach its own solution. QED.

As an aside, I have always been appalled at the use
of Fibonacci numbers to illustrate recursion, because
recursion is probably the worst[*] way to compute them.
The obvious iterative solution executes in O(n) time, and
there's also an O(1) method, albeit with some drawbacks.
Why would anyone in his right mind choose the O(e^n)
recursive method? Oh, yeah: Because he's a classroom
drudge trying to teach recursion, and it's the only
problem that comes to mind ...

The O.P.'s teacher has not chosen a good problem to
illustrate recursion, but has at least stayed away from
the hackneyed, overused, and unsuitable Fibonacci numbers.

[*] Well, "worst" isn't right, because there is always
a way to disimprove any algorithm. This worse algorithm
can itself be disimproved, and so on ad infinitum: "worst
algorithm" is like "largest integer." But among what we
might call "non-bogus" algorithms that compute Fibonacci
numbers, recursion is probably the worst.

 

[Mark Space]

You probably don't realize it, but you could start a religious war by
asking such a question

NOBODY expects the Spanish Inquisition! Our chief weapon is surprise...!

Surprise and fear...fear and surprise.... Our two weapons are fear and
surprise...!

And ruthless posting efficiency....

Our *three* weapons are fear, surprise, and ruthless efficiency...and an
almost fanatical devotion to the Fred Brooks....

Our *four*...no... *Amongst* our weapons.... Amongst our weaponry...are
such elements as fear, surprise....


I'll just post again.

 

[Taria]

Lew wrote On 10/12/07 09:04,:

Taria wrote:

Eric Sosman wrote:

No.

You've misspelled "Yes."

Recursion refers to a routine that calls itself, as with the classic Fibonacci
sequence method:

public static int fibonacci( int n )
{
if ( n < 0 ) return 0;
if ( n == 0 || n == 1 )
{
return 1;
}
return fibonacci( n - 1 ) + fibonacci( n - 2 );
}

Notice that fibonacci() calls itself, unless certain conditions are met. If
those conditions didn't exist, the recursion would never end.

Notice also that the function does exactly as I
described: It decomposes the maxi-problem of finding
fibonacci(n) into the mini-problems of fibonacci(n-1)
and fibonacci(n-2), then it combines the solutions of
those smaller problems to reach its own solution. QED.

As an aside, I have always been appalled at the use
of Fibonacci numbers to illustrate recursion, because
recursion is probably the worst[*] way to compute them.
The obvious iterative solution executes in O(n) time, and
there's also an O(1) method, albeit with some drawbacks.
Why would anyone in his right mind choose the O(e^n)
recursive method? Oh, yeah: Because he's a classroom
drudge trying to teach recursion, and it's the only
problem that comes to mind ...

The O.P.'s teacher has not chosen a good problem to
illustrate recursion, but has at least stayed away from
the hackneyed, overused, and unsuitable Fibonacci numbers.

[*] Well, "worst" isn't right, because there is always
a way to disimprove any algorithm. This worse algorithm
can itself be disimproved, and so on ad infinitum: "worst
algorithm" is like "largest integer." But among what we
might call "non-bogus" algorithms that compute Fibonacci
numbers, recursion is probably the worst.

I've always wondered why recursion performed badly for the fibonacci
numbers recursion algorithm. I've read quite a few forums on this bad
performance but no one's ever explained why. Thanks Eric, your
explanation was interesting.

Yes, I realized too, JP that the classical recursion problem usually
"added" a result (I imagine a snowball) as it backs back out after
finding its base case, when the problem I have at hand doesn't care
about the results of the other mini problems that it solved other than
it wasn't able to derive an answer in which case I'd call the routine
again with diff parms after I decide which side of the list to look
in. This is when I became confused about recursion as I expected it
to snowball into an answer when really I only care about one answer
(base case result.)

I have never differentiated between the ways recursion can be used
before (or understood it beyond textbook for that matter) till today.
I understand the directory recursion problem a lot more now (sleep
does wonders!) and I'm glad you gave me a practical approach on how to
use recursion in that way. That was a question that arose in my
mindwhile reading numerous web sites and sorting recursion java code,
(if it's such bad performance, why would anyone want to use the code
was a mystery to me but I figured it was a way to illustrate a
point.)

I would have thought having only one return in a method would be
easier to debug/maintain but as I wrote this code, it made perfect
sense why I'd have multiple returns but I wasn't sure if this was
acceptable as good coding style. I appreciate your thoughts on this.

Awesome learning experience! Thanks everyone.

-t

 

[Patricia Shanahan]

Eric Sosman wrote:
....

As an aside, I have always been appalled at the use
of Fibonacci numbers to illustrate recursion, because
recursion is probably the worst[*] way to compute them.

....

Is there a good problem for the job?

As far as I can tell, problems divide, for this purpose, into two
categories:

1. Problems that would be better done by other means.

2. Problems that are too difficult, or involve too much background
knowledge, for use in teaching the technique.

Can anyone suggest a simple problem that is both best solved by recursion?

Patricia

 

[Taria]

Eric Sosman wrote:

...> As an aside, I have always been appalled at the use

of Fibonacci numbers to illustrate recursion, because
recursion is probably the worst[*] way to compute them.

...

Is there a good problem for the job?

As far as I can tell, problems divide, for this purpose, into two
categories:

1. Problems that would be better done by other means.

2. Problems that are too difficult, or involve too much background
knowledge, for use in teaching the technique.

Can anyone suggest a simple problem that is both best solved by recursion?

Patricia

How about the factorial problem?

public static int factorial (n)
if n = 0
return 1
else
return (factorial (n*(n-1)))

I'm not very good at analyzing the time complexity of this problem so
I don't know if this is efficient or not, but this allows me to see
the recursive property to where I understand it.

 

[Patricia Shanahan]

Eric Sosman wrote:

...> As an aside, I have always been appalled at the use

of Fibonacci numbers to illustrate recursion, because
recursion is probably the worst[*] way to compute them.

...

Is there a good problem for the job?

....
How about the factorial problem?

It is indeed a popular choice.

public static int factorial (n)
if n = 0
return 1
else
return (factorial (n*(n-1)))

I think you mean "return n * factorial(n-1)".

I'm not very good at analyzing the time complexity of this problem so
I don't know if this is efficient or not, but this allows me to see
the recursive property to where I understand it.

public static int factorial(n) {
int fact = 1;
for(int i = 1; i<=n; i++) {
fact *= i;
}
return fact;
}

is more direct, and usually faster. There is no need for all those
calls. The time complexity in both cases is O(n).

Patricia

 

[Martin Gregorie]

Can anyone suggest a simple problem that is both best solved by recursion?

Yes. Tree walking.

 

[Eric Sosman]

Taria wrote On 10/12/07 14:19,:

[...]
I've always wondered why recursion performed badly for the fibonacci
numbers recursion algorithm. I've read quite a few forums on this bad
performance but no one's ever explained why. Thanks Eric, your
explanation was interesting.

I didn't really "explain" the bad performance; I
just claimed it. To understand what's going on, try
to figure out how many times you call fib(0) in the
recursive calculation of fib(n).

fib(1) is a ground case: no calls to fib(0);

fib(2) calls fib(1) and fib(0), getting to
fib(0) once.

fib(3) calls fib(2) and fib(1), making 1+0=1
calls to fib(0).

fib(4) calls fib(3) and fib(2), making 1+1=2
calls to fib(0).

fib(5) calls fib(4) and fib(3), making 2+1=3
calls to fib(0).

Does a familiar pattern begin to emerge here? Would
you care to guess how many times fib(40) will wind up
calling fib(0)?

 

[Stefan Ram]

Can anyone suggest a simple problem that is both best solved by recursion?

In my programming classes, I once had the exercise to read in
a 0-terminated sequence of numbers from the user (for example,
via the console) and print them in the reverse order. For example:

24
6
19
4
0

4
19
6
24

This exercise was given at a time, when arrays and containers
were not yet introduced, and - anyway - it also does not
contain a specific limit for the number of numbers to be read in.