RE: little off topic, need help understand a recursive call
Hi Theo,
Ramsey has a very valid point. The notion of recursion is best modeled by its
automata representations. It takes a while in most computer science curricula
for students mature enough to grasp the mathematics, but you are physicist so I
think you could dive on in. It may be a struggle at first, but it is a worthy
study. Like many relations between math and physics, the theory of computation
often presses against external states not included in simple models.
One can draw out the isNumber method using the rules of a finite state
automata. Since most OO languages including Java use a stack to manage
recursive calls, the machine is a recursive push down automata.As Ramsey
said, the states imposed on that stack by Java's Virtual Machine and runtime is
a matter that has to be either acquired by papers or empirical evidence.
V/R,
Daniel Beatty, Ph.D.,
IEEE Certified Software Development Professional (CSDP)
Computer Scientist
Code 474300D
1 Administration Circle. M/S 1109
China Lake, CA 93555
daniel.bea...@navy.mil
(760)939-7097
-Original Message-
From: webobjects-dev-bounces+daniel.beatty=navy@lists.apple.com
[mailto:webobjects-dev-bounces+daniel.beatty=navy@lists.apple.com] On
Behalf Of Ramsey Gurley
Sent: Wednesday, November 12, 2014 8:46 AM
To: Theodore Petrosky
Cc: WebObjects-Dev
Subject: Re: little off topic, need help understand a recursive call
Learning new things from new languages is fascinating. Trying to apply this
knowledge in the language you know doesn’t always go so well though. What
happens if you give isNumber a really really long string? Stack overflow :-/
Recursion is not one of Java’s strengths.
If you want a really fast isNumber and you’re only looking for chars ‘0’ thru
‘9', have a look at ERXStringUtilities.luhnCheck. Treating your chars as ints
is the fastest way I’ve found to determine isNumber. It is orders of magnitude
faster than Character.isDigit.
On Nov 12, 2014, at 4:32 AM, Theodore Petrosky wrote:
> I am trying like mad to learn more. So I have decided to put time into
> Recursive algorithms. I do not want to start a conversation whether or not
> one should or should not use recursion in this example. That is a
> conversation for another day. I don’t believe that using it here will impact
> the app at all.
>
> As an experiment I am trying to use one in my validation method. Would one of
> you great minds take a look at this. It works, but I feel I am jumping
> through too many hoops. This is my first attempt so have a little pity:
>
>
> public String validateHeight(String value) throws ValidationException {
> value = value.trim();
>
> if (!isNumber(value)) {
> throw new ValidationException("There can be only
> numbers in the Height field! (value was " + value +")");
> }
> return value;
> }
>
> private boolean isNumber(String stringToCheck) {
> if (stringToCheck.length() == 0) return true;
> if (!Character.isDigit(stringToCheck.charAt(0))) return false;
> return isNumber(stringToCheck.substring(1,
> stringToCheck.length()));
> }
>
>
> My desire is to get better at this and learning recursion is very important.
> Also, when I look at other people’s code, there are times that there are
> recursive calls and I struggle to understand them.
___
Do not post admin requests to the list. They will be ignored.
Webobjects-dev mailing list (Webobjects-dev@lists.apple.com)
Help/Unsubscribe/Update your Subscription:
https://lists.apple.com/mailman/options/webobjects-dev/daniel.beatty%40navy.mil
This email sent to daniel.bea...@navy.mil
smime.p7s
Description: S/MIME cryptographic signature
___
Do not post admin requests to the list. They will be ignored.
Webobjects-dev mailing list (Webobjects-dev@lists.apple.com)
Help/Unsubscribe/Update your Subscription:
https://lists.apple.com/mailman/options/webobjects-dev/archive%40mail-archive.com
This email sent to arch...@mail-archive.com
Re: little off topic, need help understand a recursive call
Learning new things from new languages is fascinating. Trying to apply this
knowledge in the language you know doesn’t always go so well though. What
happens if you give isNumber a really really long string? Stack overflow :-/
Recursion is not one of Java’s strengths.
If you want a really fast isNumber and you’re only looking for chars ‘0’ thru
‘9', have a look at ERXStringUtilities.luhnCheck. Treating your chars as ints
is the fastest way I’ve found to determine isNumber. It is orders of magnitude
faster than Character.isDigit.
On Nov 12, 2014, at 4:32 AM, Theodore Petrosky wrote:
> I am trying like mad to learn more. So I have decided to put time into
> Recursive algorithms. I do not want to start a conversation whether or not
> one should or should not use recursion in this example. That is a
> conversation for another day. I don’t believe that using it here will impact
> the app at all.
>
> As an experiment I am trying to use one in my validation method. Would one of
> you great minds take a look at this. It works, but I feel I am jumping
> through too many hoops. This is my first attempt so have a little pity:
>
>
> public String validateHeight(String value) throws ValidationException {
> value = value.trim();
>
> if (!isNumber(value)) {
> throw new ValidationException("There can be only
> numbers in the Height field! (value was " + value +")");
> }
> return value;
> }
>
> private boolean isNumber(String stringToCheck) {
> if (stringToCheck.length() == 0) return true;
> if (!Character.isDigit(stringToCheck.charAt(0))) return false;
> return isNumber(stringToCheck.substring(1,
> stringToCheck.length()));
> }
>
>
> My desire is to get better at this and learning recursion is very important.
> Also, when I look at other people’s code, there are times that there are
> recursive calls and I struggle to understand them.
___
Do not post admin requests to the list. They will be ignored.
Webobjects-dev mailing list (Webobjects-dev@lists.apple.com)
Help/Unsubscribe/Update your Subscription:
https://lists.apple.com/mailman/options/webobjects-dev/archive%40mail-archive.com
This email sent to arch...@mail-archive.com
Re: little off topic, need help understand a recursive call
Hi Theodore,
AFAICS there is nothing wrong with your "isNumber" method (besides that
Integer.parseInt(String s) and catching the NumberFormatException is much
shorter).
I have no proof at hand, but I remember that each recursive call has a loop
equivalent and vice versa.
So assume you have a something like
public void printNumber(int start, int stop) {
for (int i = start; i<=stop; i++) {
System.out.println(i);
}
}
You can make a recursive version like
public void printNumbersRecursive(int start, int stop) {
if (start <= stop) {
System.out.println(start);
printNumbersRecursive(start+1, stop);
}
}
In this case I would aways prefer the loop-version. It somehow feels more
natural to me.
But there are problems where recursion can be very handy. E.g. if you have
non-linear structures like trees.
Assume the following class:
public class MyNode {
private String name;
private NSMutableArray children = new NSMutableArray();
public MyNode(String name) {
this.name = name;
}
public void addToChildren(MyNode child) {
children.addObject(child);
}
}
and you build the following structure with it
public static void main(String[] args) {
MyNode root = new MyNode("root");
MyNode child1 = new MyNode("child1");
root.addToChildren(child1);
MyNode child2 = new MyNode("child2");
root.addToChildren(child2);
MyNode child11 = new MyNode("child11");
child1.addToChildren(child11);
MyNode child12 = new MyNode("child12");
child1.addToChildren(child12);
}
If you want to do something on all nodes (also called 'traversion'), e.g. write
a debug info to the console, I would code this like
public void debug() {
System.out.println("node: "+name);
System.out.println("children: [");
for (MyNode child : children) {
// recursion
child.debug();
}
System.out.println("]");
}
A call of root.debug() in the main method would produce
node: root
children: [
node: child1
children: [
node: child11
children: [
]
node: child12
children: [
]
]
node: child2
children: [
]
]
A non-recursive version of the debug method would be much more complicated.
Jm2c
C.U.CW
--
What are the three enemies of a programmer? Sunlight, oxygen, and the appalling
roar of the birds.
On 12.11.2014, at 12:32, Theodore Petrosky wrote:
> I am trying like mad to learn more. So I have decided to put time into
> Recursive algorithms. I do not want to start a conversation whether or not
> one should or should not use recursion in this example. That is a
> conversation for another day. I don’t believe that using it here will impact
> the app at all.
>
> As an experiment I am trying to use one in my validation method. Would one of
> you great minds take a look at this. It works, but I feel I am jumping
> through too many hoops. This is my first attempt so have a little pity:
>
>
> public String validateHeight(String value) throws ValidationException {
> value = value.trim();
>
> if (!isNumber(value)) {
> throw new ValidationException("There can be only
> numbers in the Height field! (value was " + value +")");
> }
> return value;
> }
>
> private boolean isNumber(String stringToCheck) {
> if (stringToCheck.length() == 0) return true;
> if (!Character.isDigit(stringToCheck.charAt(0))) return false;
> return isNumber(stringToCheck.substring(1,
> stringToCheck.length()));
> }
>
>
> My desire is to get better at this and learning recursion is very important.
> Also, when I look at other people’s code, there are times that there are
> recursive calls and I struggle to understand them.
> ___
> Do not post admin requests to the list. They will be ignored.
> Webobjects-dev mailing list (Webobjects-dev@lists.apple.com)
> Help/Unsubscribe/Update your Subscription:
> https://lists.apple.com/mailman/options/webobjects-dev/cw%40i4innovation.de
>
> This email sent to c...@i4innovation.de
>
signature.asc
Description: Message signed with OpenPGP using GPGMail
___
Do not post admin requests to the list. They will be ignored.
Webobjects-dev mailing list (Webobjects-dev@lists.apple.com)
Help/Unsubscribe/Update your Subscription:
https://lists.apple.com/mailman/options/webobjects-dev/archive%40mail-archive.com
This email sent to arch...@mail-archive.com
little off topic, need help understand a recursive call
I am trying like mad to learn more. So I have decided to put time into
Recursive algorithms. I do not want to start a conversation whether or not one
should or should not use recursion in this example. That is a conversation for
another day. I don’t believe that using it here will impact the app at all.
As an experiment I am trying to use one in my validation method. Would one of
you great minds take a look at this. It works, but I feel I am jumping through
too many hoops. This is my first attempt so have a little pity:
public String validateHeight(String value) throws ValidationException {
value = value.trim();
if (!isNumber(value)) {
throw new ValidationException("There can be only
numbers in the Height field! (value was " + value +")");
}
return value;
}
private boolean isNumber(String stringToCheck) {
if (stringToCheck.length() == 0) return true;
if (!Character.isDigit(stringToCheck.charAt(0))) return false;
return isNumber(stringToCheck.substring(1,
stringToCheck.length()));
}
My desire is to get better at this and learning recursion is very important.
Also, when I look at other people’s code, there are times that there are
recursive calls and I struggle to understand them.
___
Do not post admin requests to the list. They will be ignored.
Webobjects-dev mailing list (Webobjects-dev@lists.apple.com)
Help/Unsubscribe/Update your Subscription:
https://lists.apple.com/mailman/options/webobjects-dev/archive%40mail-archive.com
This email sent to arch...@mail-archive.com
