Recursion and Pointers
Ben Snitkoff
I'm and CS Student in high school, and I was wondering if it is as common in
Java to use recursion as it is in C or C++. I know that Java supports
multi-threading, making it good for sorts, and things of the like, so does
that make Recursion useless in Java? Also, is there anyway to dy dynamic
data without pointers? If Java is to be used to make full featured apps
doesn't it need something like that? I remember from APCS pointers while
making binary search trees and linked lists were about the coolest and most
efficient things you could use.
Thanks
Ben
Jon Skeet
Java is *full* of pointers - or rather, references, which are either
pointers to objects or null - it just doesn't have any pointer
*arithmetic*.
I don't see much link between recursion and multi-threading - recursion
is certainly still used in Java.
--
Jon Skeet - <sk...@pobox.com>
http://www.pobox.com/~skeet/
If replying to the group, please do not mail me too
Gordon Beaton
> I'm and CS Student in high school, and I was wondering if it is as
> common in Java to use recursion as it is in C or C++. I know that
> Java supports multi-threading, making it good for sorts, and things
> of the like, so does that make Recursion useless in Java?
Multithreading and recursion are completely unrelated to one another.
Recursion is just as useful in Java as it is in C, for essentially the
same set of problems.
> Also, is there anyway to dy dynamic data without pointers?
Of course. Java uses references, which even though they aren't
necessarily addresses, are for most intents and purposes equivalent to
pointers and can be used in most situations where a C programmer would
have used a pointer.
> If Java is to be used to make full featured apps doesn't it need
> something like that? I remember from APCS pointers while making
> binary search trees and linked lists were about the coolest and most
> efficient things you could use.
Like anything else, they are only efficient when they are the right
tool for the job. It all depends on what problem you are trying to
solve.
/gordon
--
[ do not send me private copies of your followups ]
g o r d o n . b e a t o n @ e r i c s s o n . c o m
ericsson research
stockholm, sweden
Patricia Shanahan
Gordon Beaton wrote:
...
> > Also, is there anyway to dy dynamic data without pointers?
>
> Of course. Java uses references, which even though they aren't
> necessarily addresses, are for most intents and purposes equivalent to
> pointers and can be used in most situations where a C programmer would
> have used a pointer.
...
Indeed, unless you consider the features of C pointers to be the exact
definition of pointer, Java has pointers. It has pointers in the same
sense, for example, as Pascal.
It is the single most pointer-orientated language I've ever programmed
in, because there is no way to assign an object to a variable, only a
pointer to the object.
The limitations are that it does not support pointers to primitives and
forces pointers to point only to objects of appropriate class for the
type of the pointer. It also does not have pointer arithmetic. It does
not support pointer arithmetic.
Patricia
Marshall Spight
news:B7BCCA51.2DA2%sni...@mac.com...
> Hello,
>
> I'm and CS Student in high school, and I was wondering if it is as common
in
> Java to use recursion as it is in C or C++.
I have come across uses of recursion in Java code about as often as
I used to come across it in C or C++ code: hardly ever.
Recursion is a very cool concept and important for a general
understanding of program execution, but it is not an
every-day kind of technique.
> I know that Java supports
> multi-threading, making it good for sorts, and things of the like, so does
> that make Recursion useless in Java?
No; it's still useful. Multi-threading and recursion don't really
adress the same issues.
> Also, is there anyway to dy dynamic
> data without pointers? If Java is to be used to make full featured apps
> doesn't it need something like that? I remember from APCS pointers while
> making binary search trees and linked lists were about the coolest and
most
> efficient things you could use.
The differences between pointers and references are minimal when
you are talking about code that is working. There are some
things that are harder to do with references than with pointers:
I remember years ago, a friend showed me some C code that
was triggered when it detected an unauthorized use.
// unauthorized use detected;
int *p = 10000;
while (true)
{
// search for an access violation.
*p = 0;
p = p*2;
}
You just can't write code like that in Java. :-)
[this presents no safety issues for a memory-protected OS,
for those of you used to less-robust desktop OSs that
might be concerned.]
Dynamic data is easy in Java. All you need is "new".
Or look at java.util.Vector, which is a dynamically
sizeable array.
Marshall
Ben Snitkoff
LMNl7.51786$sa.31...@news1.rdc1.sfba.home.com, "Marshall Spight"
<mars...@meetstheeye.com> wrote:
> No; it's still useful. Multi-threading and recursion don't really
> adress the same issues.
Well, in that case I was mistaken, could someone then explain to me the
difference between Multi-Threading and recursion?
Thanks!
Ben
Tor Iver Wilhelmsen
> The limitations are that it does not support pointers to primitives
A one-element array of primitives can be seen as the functional
equivalent to a pointer to them (the indirection). "Derefing" is a bit
more awkward, though.
> and forces pointers to point only to objects of appropriate class
> for the type of the pointer.
An Object reference is the functional equivalent of a void (untyped)
pointer. It can even hold one of the aforementioned
"primitive-pointers" (e.g. Object o = new int[1];) :-P
> It also does not have pointer arithmetic. It does not support
> pointer arithmetic.
Pointer arithmetic for any other purpose than array-like things is
evil <g>, and Java has arrays.
--
Tor Iver Wilhelmsen <to...@chello.no>
Shit happens. Everything else is illusion.
Tor Iver Wilhelmsen
> Well, in that case I was mistaken, could someone then explain to me the
> difference between Multi-Threading and recursion?
In layman terms:
Multithreading: A lot of (possibly) different stuff happens at
(almost) the same time. (That is, you have several threads of
execution, each of which _independently_ run code. If it's the same
method, then that only matters to any non-local variables affected by
the call.)
Recursion: Approximately the same thing happens over and over again in
the same thread of execution. (That is, a method invokes itself,
hopefully with some condition which eventually wil stop it from doing
so so that the call(s) can "unwind".)
Chris Smith
> Well, in that case I was mistaken, could someone then explain to me the
> difference between Multi-Threading and recursion?
That's hard until we know why you thought they were analogous. You've
just asked something equivalent to "if they're not the same thing, then
what exactly *is* the difference between love and a car door?" It's
difficult to give a useful answer without understanding why you thought
the two were the same.
Essentially, recursion is a way to approach a task, in which a problem is
broken down into smaller but equivalent problems, until you can solve any
larger problem by solving a smaller easy version of the same.
Multithreading is the ability to do several things at what at least
appears to be the same time, all in the same program. Were you
miunderstanding one or the other?
Chris Smith
Carlos Portela
Multi-threading refers to the ability to perform multiple tasks at the same
time.
Recursion refers to a technique used in programming where a function calls
itself one or more times until some condition is met and the stack of calls
gets rewound and the original function call returns to its caller.
May you be confused about re-entrancy?
Carlos
"Ben Snitkoff" <sni...@mac.com> wrote in message
news:B7BD4A93.2E78%sni...@mac.com...
Greg Faron
>
> Recursion: Approximately the same thing happens over and over again in
> the same thread of execution. (That is, a method invokes itself,
> hopefully with some condition which eventually wil stop it from doing
> so so that the call(s) can "unwind".)
What about end-recursion? I seem to remember that C++ had a nifty
efficiency trick in which all the local variables of the previous call
would be returned to freestore if the recursive statement took place at
the end. For example, this trivial method is end-recursive:
double eval(double x)
{
if (x < 0.0)
return x;
else
return eval(x - 1.0);
}
but this would not be end-recursive:
double eval(double x)
{
if (x < 0.0)
return x;
else
{
double y = eval(x - 1.0);
return y;
}
}
It's true that there's nothing in the example above that would need to
go back to freestore ("new" or "malloc" weren't used), but I believe the
efficiency was also reflected in the stack trace.
Does Java offer this optimization (for that matter, does C++ offer it
or was I imagining it)?
--
Greg Faron
Integre Technical Publishing Co.
ar...@hpcvplnx.cv.hp.com
> That's hard until we know why you thought they were analogous. You've
> just asked something equivalent to "if they're not the same thing, then
> what exactly *is* the difference between love and a car door?"
It's easier to get in and out of a car door? ;-)
John Creighton
Chris Smith wrote:
> Ben Snitkoff wrote ...
> > Well, in that case I was mistaken, could someone then explain to me the
> > difference between Multi-Threading and recursion?
>
> That's hard until we know why you thought they were analogous. You've
> just asked something equivalent to "if they're not the same thing, then
> what exactly *is* the difference between love and a car door?"
I saw an example of recurssion before that was kind of like multithreading.
Perhaps it may be simmilar to what the OP was thinking of. The profferser
had a deck of cards: he gave half the deck to one person and half the deck
to another person. Each person that recieved a part of a deck divided the
deck
in half and gave each half to another person. This went on untill there was
only
two cards left. At which point the cards were shuffled. Clearly threads are
not
needed for this example. However in this case each of the recursive steps can
be done indpendently because there is no dependencies between the steps.
@rigidsoftware.com C. Lamont Gilbert
received changed references from parameters passed into function calls.
"Tor Iver Wilhelmsen" <to...@chello.no> wrote in message
news:wk7kvcr...@mail.multinett.no...
@rigidsoftware.com C. Lamont Gilbert
"Carlos Portela" <cmpo...@simple-sw.com> wrote in message
news:BhSl7.4090$uO6.6...@typhoon.jacksonville.mediaone.net...
> Hi Ben,
>
> Multi-threading refers to the ability to perform multiple tasks at the
same
> time.
>
> Recursion refers to a technique used in programming where a function calls
> itself one or more times until some condition is met and the stack of
calls
> gets rewound and the original function call returns to its caller.
>
Sounds a lot like life.
Lee Fesperman
>
> yes, I use the single dimension array often. its a quite nice trick to
> received changed references from parameters passed into function calls.
Sounds like you're doding C/C++ programming in Java. It really is bad form; none of the
Java APIs use it. I've written great gobs of 'systems' code in Java (as well as other
types) and have yet to find an occasion where I needed it.
--
Lee Fesperman, FFE Software, Inc. (http://www.firstsql.com)
===================================================================
* Check out Database Debunkings (http://www.firstsql.com/dbdebunk/)
* "Where Persistent Prevailing Database Fallacies Are Dispelled"
Patricia Shanahan
Tor Iver Wilhelmsen wrote:
...
> Pointer arithmetic for any other purpose than array-like things is
> evil <g>, and Java has arrays.
>
> --
> Tor Iver Wilhelmsen <to...@chello.no>
> Shit happens. Everything else is illusion.
I don't agree that non-array pointer arithmetic is always evil. For
example, I once worked on the dynamic storage allocator for use inside
an operating system. The distribution of sizes of allocations varied
depending on the workload, so it did splitting and coalescing of blocks.
That involved pointer arithmetic.
I still don't know of any better way of doing it.
Patricia
Chris Smith
> I saw an example of recurssion before that was kind of like multithreading.
> Perhaps it may be simmilar to what the OP was thinking of. The profferser
> had a deck of cards: he gave half the deck to one person and half the deck
> to another person. Each person that recieved a part of a deck divided the
> deck
> in half and gave each half to another person. This went on untill there was
> only
> two cards left. At which point the cards were shuffled. Clearly threads are
> not
> needed for this example. However in this case each of the recursive steps can
>
> be done indpendently because there is no dependencies between the steps.
Yes, okay... recursive algorithms are definitely a lot easier to make
parallel than a lot of other kinds of algorithms, for exactly this
reason: most of the time, there are no core functional dependencies
between the broken-down pieces of the problem.
I recall seeing (and using, at some point), a modification of C that
supported a limited kind of asynchronous method call that was supposed to
be lightweight and support this kind of parallelism. I recall that a
very successful chess implementation was written in the language by
parallelizing the minimax search. I've since forgotten the name of the
language and the chess program.
Chris Smith
Gordon Beaton
> What about end-recursion? I seem to remember that C++ had a nifty
> efficiency trick in which all the local variables of the previous
> call would be returned to freestore if the recursive statement took
> place at the end. For example, this trivial method is end-recursive:
The optimization you are describing is called last call optimization,
and it's used in languages like Prolog and Erlang where recursion is
the "normal" loop structure. If a function is tail recursive (i.e. the
very last operation in the function is a recursive call), the local
variables aren't needed afterwards so the current stack frame can be
reused for the recursive call. Since the stack doesn't grow, tail
recursion can be infinite.
> Does Java offer this optimization (for that matter, does C++ offer
> it or was I imagining it)?
Potentially last call optimization could be used in any language that
uses a stack, it's up to the compiler. I don't know if any C++
compiler does so and don't think that Javac does either.
Kurt M. Alonso
Greg Faron wrote:
> What about end-recursion? I seem to remember that C++ had a nifty
> efficiency trick in which all the local variables of the previous call
> would be returned to freestore if the recursive statement took place at
> the end. For example, this trivial method is end-recursive:
>
The correct term is tail recursion. All it takes to implement it in your
example
is to replace the parameter x with x-1.0 in the stack and "jump" (not call)
to
the beginning of the function. You save stack and back-jumping when
returning the value.
Most C/C++ compilers implement tail recursion, which can be generally
applied when the last executed statement of a function is a call to another
(side-effect free) function. I do not really know about the javac compiler,
but
it is a widely used compiler optimization technique, probably dating from
the
days of John McCarthy and Lisp.
Jon Skeet
> > Does Java offer this optimization (for that matter, does C++ offer
> > it or was I imagining it)?
>
> Potentially last call optimization could be used in any language that
> uses a stack, it's up to the compiler. I don't know if any C++
> compiler does so and don't think that Javac does either.
Note that Java would still need to maintain a stack for purposes of
traces etc, which removes at least a *bit* of the advantage.
tam
As you've described it the example does indeed use both threads and recursion.
First there is one thread of control, the professor dividing the deck.
After the professor handes the deck to two different people A and B, we have two
threads. Person A is acting independently of person B. When A and B hand off
the cards to AA, AB, BA and BB we get four threads.
In this example the fact that the various people can act simultaneously and
independently is
the essence of multithreading. The fact that the action we take at each step
is in basically the same as we took in the step before -- working on some subset
of the problem with some special terminal action -- is the
essence of the recursion.
To illustrate multi-threading without recursion we might have the professor hand
out a deck of cards to each student and have each of them play a game of solitaire.
To illustrate recursion without threading, we might have the
professor use the same algorithm for sorting as above, but keeping track of all
of the piles himself on his desk rather than handing them to the students.
Regards,
Tom McGlynn
Greg Faron
> > function calls itself one or more times until some condition
> > is met and the stack of calls gets rewound and the original
> > function call returns to its caller.
>
> Sounds a lot like life.
The AI program or the Milton Bradley game?
--
Greg
Jezuch
wrote:
>A one-element array of primitives can be seen as the functional
>equivalent to a pointer to them (the indirection).
That's great if I need a mutable final primitive :) For example - when I
need to access and modify it in an anonymous inner class...
--
Ecce Jezuch
http://free.polbox.pl/j/jezuch - Kronika paranoika
"No matter what you believe, we don't believe in you
We hate everyone" - P. Ratajczyk AKA P. Steele
Carl Howells
> What about end-recursion? I seem to remember that C++ had a nifty
> efficiency trick in which all the local variables of the previous call
> would be returned to freestore if the recursive statement took place at
> the end. For example, this trivial method is end-recursive:
>
> double eval(double x)
> {
> if (x < 0.0)
> return x;
> else
> return eval(x - 1.0);
> }
>
> but this would not be end-recursive:
Yes it would. Any sane compiler will optimize out the extra assignment in
there.
> double eval(double x)
> {
> if (x < 0.0)
> return x;
> else
> {
> double y = eval(x - 1.0);
> return y;
> }
>
> }
>
> It's true that there's nothing in the example above that would need to
> go back to freestore ("new" or "malloc" weren't used), but I believe the
> efficiency was also reflected in the stack trace.
>
> Does Java offer this optimization (for that matter, does C++ offer it
> or was I imagining it)?
Tail-recursion to loop optimization isn't done in sun's javac compiler...
It should be, but it isn't. It is done in some C compilers. It is done in
just about ALL compilers for functional languages.
I suppose it's theoretically possible that some JVM's do that optimization,
but that seems unlikely.
Chris Smith
>
> Tail-recursion to loop optimization isn't done in sun's javac compiler...
> It should be, but it isn't. It is done in some C compilers. It is done in
> just about ALL compilers for functional languages.
Do you know of any that don't? I should think we'd need to avoid them
like the plague! :)
> I suppose it's theoretically possible that some JVM's do that optimization,
> but that seems unlikely.
As Jon pointed out, the need to build stack traces on demand mitigates
the benefits of tail-recursion somewhat. The space for local variables
can be reclaimed, but identifying information about the stack frame must
remain. It's still possible, but it leaves tail-recursion as a resource-
consuming operation... it's quantitively better, but not qualitatively so
as it is elsewhere.
Chris Smith
Tom Anderson
> Carl Howells wrote ...
>
> > Tail-recursion to loop optimization isn't done in sun's javac compiler...
> > It should be, but it isn't.
> > I suppose it's theoretically possible that some JVM's do that optimization,
> > but that seems unlikely.
personally, i'd say that this optimisation, like all other optimisation,
belongs in the JIT, not in javac. i think it's useful (for debugging etc)
to have a very simple, straightforward transformation from source to
bytecode, and to have all the optimisations in one place, under the
control of the JVM's profiler. but, i admit, this is really an improperly
thought out knee-jerk opinion.
> As Jon pointed out, the need to build stack traces on demand mitigates
> the benefits of tail-recursion somewhat. The space for local
> variables can be reclaimed, but identifying information about the
> stack frame must remain. It's still possible, but it leaves
> tail-recursion as a resource- consuming operation...
i know it's monday morning, but it seems to me that all you'd need to
record is the depth of the recursion, which could be a single int,
incremented every time round the loop; the part of the stack trace
corresponding to the nested calls could then be generated by sticking that
number of copies of the line info together. for instance, consider this
class:
public class Recurse
{
public static void main( String[] args )
{
recurse() ;
}
private static void recurse()
{
if (Math.random() > 0.8)
throw new RuntimeException( "Stopped!" ) ;
recurse() ;
}
}
this produces the following output:
Exception in thread "main" java.lang.RuntimeException: Stopped!
at Recurse.recurse(Recurse.java:11)
at Recurse.recurse(Recurse.java:12)
at Recurse.recurse(Recurse.java:12)
at Recurse.recurse(Recurse.java:12)
at Recurse.recurse(Recurse.java:12)
at Recurse.recurse(Recurse.java:12)
at Recurse.recurse(Recurse.java:12)
at Recurse.recurse(Recurse.java:12)
at Recurse.recurse(Recurse.java:12)
at Recurse.main(Recurse.java:6)
the eight lines of "at Recurse.recurse(Recurse.java:12)" could be
autogenerated. a bit like this:
public class Recurse
{
public static void main( String[] args )
{
recurse() ;
}
private static void recurse()
{
int depth = 0 ;
while (true)
{
if (Math.random() > 0.8)
throw new RuntimeException( ("Stopped! at depth " + depth) ) ;
++depth ;
}
}
}
but instead of putting the depth in the message, it would be used to fake
up a stack trace.
nb i don't guarantee freedom from off-by-one errors in the above code :)
tom
--
Per Dementia ad Astra
Chris Smith
> personally, i'd say that this optimisation, like all other optimisation,
> belongs in the JIT, not in javac. i think it's useful (for debugging etc)
> to have a very simple, straightforward transformation from source to
> bytecode, and to have all the optimisations in one place, under the
> control of the JVM's profiler. but, i admit, this is really an improperly
> thought out knee-jerk opinion.
I agree. I actually wish that bytecode were more expressive. We're
kinda stuck with it now, but in more enlightened times, bytecode could
have been designed to make looping structures explicit as is done in many
intermediate languages for compilers, instead of using an assemply-
language model. However, it took Sun a while to realize that treating
bytecode as portable assembly language is counterproductive to
performance.
> i know it's monday morning, but it seems to me that all you'd need to
> record is the depth of the recursion, which could be a single int,
> incremented every time round the loop;
Actually, yes I think you're right. It hadn't occurred to me.
Chris Smith
Gordon Beaton
> Tom Anderson wrote ...
> > i know it's monday morning, but it seems to me that all you'd need to
> > record is the depth of the recursion, which could be a single int,
> > incremented every time round the loop;
>
> Actually, yes I think you're right. It hadn't occurred to me.
Note that this is only a special case.
Recursion doesn't have to be restricted to a single function, there
can be any number of functions involved. Think of the way a simple
recursive descent parser works - a function for each non-terminal in
the language, and as tokens are consumed they call each other in a
mutually recursive manner.
In fact the idea of last call optimization applies to other situations
than just tail recursive functions; it can be used in any situation
where the local stack frame won't be needed again after the last call.
It's unfortunate that you need to maintain a stack just in case an
exception occurs. Maybe a circular buffer could be used for that
instead, and information about the first M and last N calls
(configurable, of course) in the stack would be sufficient.
Jon Skeet
Sure - multithreading is when you have two or more threads of execution
running "at the same time" (more accurately for single processor
machines, they just look like they're doing that). For instance, one
thread could be listening for GUI events and another thread doing some
calculation or fetching a web page.
Recursion is where a method calls itself, or various methods all call
each other. For instance, a simple (and not recommended) way of
calculating fibonacci numbers is:
public int fib (int n)
{
if (n < 3)
return 1;
return fib (n-1)+fib (n-2);
Mike Schilling
>
> Gordon Beaton wrote:
> ...
> > > Also, is there anyway to dy dynamic data without pointers?
> >
> > Of course. Java uses references, which even though they aren't
> > necessarily addresses, are for most intents and purposes equivalent to
> > pointers and can be used in most situations where a C programmer would
> > have used a pointer.
> ...
>
> Indeed, unless you consider the features of C pointers to be the exact
> definition of pointer, Java has pointers. It has pointers in the same
> sense, for example, as Pascal.
Precisely like Pascal, in fact. Just as in Pascal, you can't create a
pointer to an existing object; you can only get a pointer when creating
a dynamic object. The main difference is that in Pascal you can have
dynamic variables of any type, while in Java objects are always dynamic
but scalars never dynamic (viewing arrays of scalars as objects.)