Re: Recursion Usage and Concepts - Newbie Question

Taria schrieb:
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! :p)

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

-t


Recursion is only if a function calls itself. What you are talking about
is one of the typical algorithm design paradigms to solve a problem:
"Divide and Conquer"
there are some other Algorithm paradigms that may use recusrsion to work.
Another paradigm that uses recursion is Dynamic Programming.
While you can do the devide and conquer in static method calls Dynamic
programming needs some kind of object that holds results of earlier
computed values. So either create an object that does the computation
and holds these values .. or you have to pass this computed values with
each methodcall..

In other parts of the thread we had the fibonacci series..
with only Divide and Conquer you will get exponential nr of method calls
while if you are using dynamic programming and store solved subproblems
you stay in O(n) (which is quite bad for fibonacci but better than
nothing..)

Christian
.

Relevant Pages

  • Recursion Usage and Concepts - Newbie Question
    ... I'm struggling with an assignment that involves using a 'quicksort' ... use of recursion is a requirement of this assignment. ... few examples of other ppl's recursive Java routines, ... question my pursuit of using static methods. ...
    (comp.lang.java.programmer)
  • Re: Response to Karen and to Willem on recursive proofs
    ... > Could you give an example of a correctness proof involving recursion? ... // But since it can be seen by inspection of the loop termination condition ... // Recursion in programming is, of course, a subroutine calling itself. ...
    (comp.programming)
  • Re: CAS, Lambda Calculus, Continuation and Functional Programming
    ... There are no expressions in Fortran or Pascal??! ... expressions are programming language constructs that return a value. ... > languages don't have recursion. ...
    (sci.math.symbolic)
  • Re: Another way to do x^n
    ... think carefully about writing code readable by folks who aren't Forth ... But the Forth programming culture is one of egotistical cleverness, ... Very handy for things like parsers. ... But there are enormous application areas where recursion is of no advantage, and its employment just obfuscates the code. ...
    (comp.lang.forth)
  • Re: Interesting article by Joel Spolsky: The Perils of JavaSchools
    ... > recursion to define an ordered set, that does not imply (as you imply ... programming in something like Java. ... >>> abandon Java in favour of a toy language that is limited to them and no ...
    (comp.programming)