Recursion Usage and Concepts - Newbie Question

[Lew]

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.

That is one of the two best paraphrases of that routine I've seen in these
groups. Actually, on balance it's better than the other one - that is the
best paraphrase of that routine I've seen in these groups.

 

[Steve Wampler]

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

Heh. I assigned something like that once (not in Java, but translates
well). The 'cleverest' solution turned in was generally (ignoring
possible failure of obtaining console and any typos):

public static void main(String args[]) {
String line = null;
if (null != (line = System.console().readLine())) {
main(args);
System.writeln(line);
}
}

Wasn't what I was looking for, but showed recursion and a
good understanding of how methods/functions work.
(The original solution was in a language "Icon" and was
simply:

procedure main()
write(1(read(),main()))
return
end
)

 

[Lew]

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

Tail recursion can always be refactored to a loop with little difficulty.
<http://en.wikipedia.org/wiki/Tail_recursion>

 

[Patricia Shanahan]

Yes. Tree walking.

Are trees usually introduced before recursion?

Patricia

 

[Stefan Ram]

Are trees usually introduced before recursion?

The problem might be: to determine for
a directory given by an object of type

http://download.java.net/jdk7/docs/api/java/io/File.html

whether it contains (directly or indirectly in
any subdirectory) any file with an underscore
in its name.

It is sufficient to give the above documentation as
a reference. No need to explicitly introduce trees
before. (Most pupils in a programming class already
have heard the term »directory« and »file« before).

 

[Mark Space]

That is one of the two best paraphrases of that routine I've seen in
these groups. Actually, on balance it's better than the other one -
that is the best paraphrase of that routine I've seen in these groups.

^_^

Which is kind of surprising considering how little actual paraphrasing I
did. I added the word "post" a couple of times and substituted Fred
Brooks for the Pope. Incorrectly, I see, because I left the word "the"
in there, dang it.

 

[Patricia Shanahan]

The problem might be: to determine for
a directory given by an object of type

http://download.java.net/jdk7/docs/api/java/io/File.html

whether it contains (directly or indirectly in
any subdirectory) any file with an underscore
in its name.

It is sufficient to give the above documentation as
a reference. No need to explicitly introduce trees
before. (Most pupils in a programming class already
have heard the term »directory« and »file« before).

I like that one. It does meet both the requirements I suggested earlier.

Patricia

 

[Roedy Green]

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.

You an do factorial more efficiently with iteration. Way back in the
olden days of Fortran I wrote an iterative version of QuickSort. It
was hideously more complicated though.

Recursion is pretty well the only way to traverse a tree (e.g.
enumerate all the files in a directory tree).

 

[Thomas Fritsch]

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?

I'd suggest the Towers of Hanoi.
<http://en.wikipedia.org/wiki/Tower_of_Hanoi>

 

[Martin Gregorie]

Are trees usually introduced before recursion?

I think I was introduced to trees and recursion at nearly the same time,
but it was a long time ago and I don't really remember. I'm pretty
certain factorial() was the first recursive example I saw, but the first
useful examples of recursion I met were connected with building and
walking ordered binary trees - quite probably they were in Nicolas
Wirth's book "Algorithm + Data Structure = Program".

 

[Stefan Ram]

but it was a long time ago and I don't really remember. I'm pretty

From a pure factual perspective, there is no need to
explicitly teach recursion, once it has been taught that

- A method might invoke a method

- Each method invocation has a fresh compound
of local variables (aka »activation record«
or »incarnation« or »block instance« or
»instance« of the method)¹

(The second assumptions fails for certain languages, such as
old FORTRAN or BASIC. So, when one has first learned such an
old language and now learns Java, he needs to learn the second
fact about the local variables.)

The other perspective is, of course, that pupils will not
always be able to immediatly see all relevant implications of
these two facts, so recursion needs to be taught. Moreover, it
also helps to clarify and test the understanding of both of
these facts.

When I teach recursion, sometimes - as an intermediate
step - I introduce redundant functions first.

For example, a method, that can print 0, 1, 2, or 3 asterisks:

public static void print( final int number )
{ if( number > 0 )
{ java.lang.System.out.print( '*' );
print1( number - 1 ); }}

public static void print1( final int number )
{ if( number > 0 )
{ java.lang.System.out.print( '*' );
print2( number - 1 ); }}

public static void print2( final int number )
{ if( number > 0 )java.lang.System.out.print( '*' ); }

These are kinds of »static incarnations« - each
incarnation has method declaration in the source code.

From there, the step towards recursion is the observation
that the three function declarations are nearly identical
and, thus, can be merged as one.

1) Objects, historically, were generalisations of
method incarnations - namely, class declarations
were generalisations of procedure declarations:

»A procedure which is capable of giving rise to block
instances which survive its call will be known as a class;
and the instances will be known as objects of that class.«

»3.« in »III. Hierachical Program Structures«
Ole-Johan Dahl und C. A. R. Hoare, Seite »179« in

http://portal.acm.org/ft_gateway.cfm?id=1243383&type=pdf

 

[Eric Sosman]

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?

Perhaps a program to play a fairly simple game like
tic-tac-toe ("naughts and crosses") would be a candidate.
Yes, it's a tree search and the beginning student may not
yet know about trees, but it seems to me the problem could
be posed and discussed and solved without using the word
"tree" at all.

Any kind of partitioning sort might do well, if "sort"
won't scare the students. For arrays a radix sort or a
Quicksort seems a reasonable problem. If knowledge of
linked lists can be assumed, sorting them with a top-down
straight merge is an easy recursion (whether it's best or
not depends on what you mean by "best").

Recursive-descent parsing might be too intricate for
someone who hasn't yet met recursion, but maybe a simple
expression evaluator: Numeric operands only, all operators
at equal precedence. Think of it as a four-function
calculator with ( ) keys to invoke and terminate sub-
instances of itself. ("Best solution" is debatable again,
though; an explicit stack is probably more convenient.)

 

[Daniel Pitts]

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;
}

Probably the same reason you feel like having unnecessary variables...

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

 

[Daniel Pitts]

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.

You can have as many return statements in your code as make sense, but
only the first one that gets executed will do anything...

public String bob(int value) {
if (value == 0) {
return "Foo";
}
if (value < 2) {
return "Bar";
}
if (value > 2) {
return "Baz";
}
return "Value is 2!";
}

There is a school of thought, which I disagree with completely, that
your should have exactly one exit point from a function/procedure. They
would have you write the above code like:

public String bob(int value) {
final String result;
if (value == 0) {
result = "Foo";
} else if (value < 2) {
result = "Bar";
} else if (value > 2) {
result = "Baz";
} else {
result = "Value is 2!";
}
return result
}

In my opinion, that is actually more complicated to understand. On the
other hand, if you have a method that is 100 lines long, and a return
statement somewhere in the middle, you can confuse people who don't
notice that return. In practice, that doesn't matter, because you
shouldn't have methods that are longer than, say, 15 lines (give or
take). If you're writing a method thats long, try to think about the
subtasks inside of it, and breaking them out into their own methods.

Hope this helps,
Daniel.

 

[Daniel Pitts]

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.

xkcd on Monty Python quotes:
http://xkcd.com/16/

 

[Daniel Pitts]

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.

This is actually a space complexity issue. If you called factorial 500,
you'd end up with a stack 500 deep. Actually, in this case you'd also
end up with an integer overflow, but lets assume you're using a special
int that can hold 500! (hint, BigInteger can)

For these reasons, Factorial is best solved iteratively too.
public static int factorial(int n) {
int f = 1;
while (n > 1) {
f *= n--;
}
return f;
}

I think tree traversal is probably one of the better examples of
recursion, but it implies understanding of trees.

 

[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;
}

Probably the same reason you feel like having unnecessary variables...

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

Well, I could say that I felt it unnecessary to point out every example, and
that I should leave one for you to find.

 

[Lasse Reichstein Nielsen]

Tail recursion can always be refactored to a loop with little difficulty.
<http://en.wikipedia.org/wiki/Tail_recursion>

But the traditional recursive factorial isn't tail-recursive. It calls
recursively and then multiplies the result afterwards.

However, if you write it with an accumulator, it will be.
This is a tail-recursive version corresponding to Patricia Shananhan's
Java-code.

fun factorial(n) =
let fun fact_for(fact, i) = if (i <= n)
then fact_for(fact * i, i + 1)
else fact
in fact_for(1, 1)

/L

 

[Lasse Reichstein Nielsen]

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)?

Yes, that's the inductive argument. The inductive methods can usually
be handwaved. More formally:

A call to fib(n) makes fib(n)-1 additions.
This is the case for the base cases (0 additions, just return 1).
For a non-base-case (n>1), it makes two calls, to fib(n-1) and
fib(n-2) and adds these. If these use fib(n-1)-1 and fib(n-2)-1
additions, then calculating the result uses a total of
(fib(n-1)-1)+(fib(n-2)-1)+1
= fib(n-1)+fib(n-2)-1 =
= fib(n)-1
additions.

Or more handwavy: Notice that the only constant occuring in an
addition is 1, and that nowhere is a calculated value used more
than once, so the result is found by adding 1's until you reach
fib(n).
This is the version that enlightened me

/L

 

[Roedy Green]

For these reasons, Factorial is best solved iteratively too.

for three different factorial algorithms see
http://mindprod.com/jgloss/factorial.html