• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

An odd question...

 
Sam Smoot
Ranch Hand
Posts: 238
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok, this is, but isn't a homework question. I am looking for ideas or examples of how to write a recursive method that doesn't depend on local or global storage to work. I don't want to post the problem here because, yes, I do want to figure it out, but I can't seem to find any good examples of a functional programming type of recursion in JAVA.

The method would basically have to have the following type of structure:

public static int recmeth(int arg1, int arg2){
// No locally defined storage (int x = 0, etc.) or IF / Loop structure.
// Only a recursive call.
?
return result
}

 
David Harkness
Ranch Hand
Posts: 1646
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I suppose it depends on the calculation you're trying to make. In some cases couldn't you pass the "local state" on to each iteration? The factorial method is a classic recursive algorithm that doesn't require any local or global storage.Hmm, I see now your comment bars any if tests. Well, since a recursive algorithm requires a stop condition, how will you detect it without an if test of some sort?
 
Sam Smoot
Ranch Hand
Posts: 238
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
As a "general" hint, I'm reading an array.

 
David Harkness
Ranch Hand
Posts: 1646
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Sam Smoot:
As a "general" hint, I'm reading an array.
I don't see how that changes anything. Every recursive algorithm requires a stop condition. Without one, you have infinite recursion. And a condition implies branching logic: an if test or ternary statement.
 
Sam Smoot
Ranch Hand
Posts: 238
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I understand that, and I have posed the same question to the instructor as to if we can use IF... Should be able to, but..

 
M Beck
Ranch Hand
Posts: 323
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i'm not an expert on functional programming (though i'd like to learn more about it), but... from all the examples of it i've seen, recursion in languages like Scheme and Lisp certainly does depend on conditional tests, e.g., COND statements and the like.

now ML and Haskell might use different syntax, and the tests in them might be stated in a more implicit fashion (i know even less about ML than Scheme), but that doesn't mean there's not a test being done. if you declare an ML function to be (for example) zero when its argument is such-and-so, and a function of itself when the argument is otherwise, it's still understood that the computer will have to test the argument and conditionally decide what to do based on the outcome. the computer runs machine code, not SML-NJ.

even completely declarative programming (Prolog, say) still involves conditional tests, although the syntax might hide them. you couldn't have Turing equivalence without them, i don't think.
 
Hung Yee
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How about using the switch statement? It's essentially another way of doing conditional logic.
 
Sam Smoot
Ranch Hand
Posts: 238
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
DON'T EVEN MENTION PROLOG!!! We already went down that route and my brain still hurts... I did get more information from the instructor and, since IF is a Function, it is allowed (YEAH!). Now to just figure out the implementation.. :roll:

We are currently looking at Scheme which seems much more friendlier than Prolog, but it is still a new twist for this old dog...

Any other suggestions are appreciated, and I'll post the results (should I finally get it working) after the assignment is over....
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You can make a recursive function to reverse the elements in an array with one if test and no local variables, too. Given "A,B,C" returns "C,B,A".
 
Praveen Balaji
Ranch Hand
Posts: 60
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Let it go past the end of the array and throw an exception. Catch the RuntimeException from the caller.



Is it Friday already? all these disillusions!!
 
David Harkness
Ranch Hand
Posts: 1646
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by praveen balaji:
Let it go past the end of the array and throw an exception. Catch the RuntimeException from the caller.
A try-catch block still contains branching logic (conditional expression). No matter what language you use, the computer at its core still has a decision to make: recurse again or return a result.
 
Kevin Stock
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Sam Smoot:
Ok, this is, but isn't a homework question.


Would this happen to be Schrodinger's Homework?
 
David Harkness
Ranch Hand
Posts: 1646
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Kevin Stock:
Would this happen to be Schrodinger's Homework?
Yes, and his cat did or did not eat it.
 
Sam Smoot
Ranch Hand
Posts: 238
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is what I turned in, got 100 , though there may be some leeway in the grading...

This was using the 1.5 JDK installation...

 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Very nice news on the grade! Congratulations! Keep having fun! (cause otherwise you'll turn into Walley.)
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic