wood burning stoves 2.0*
The moose likes Beginning Java and the fly likes Help with simple Recursive functions Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Soft Skills this week in the Jobs Discussion forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Help with simple Recursive functions" Watch "Help with simple Recursive functions" New topic
Author

Help with simple Recursive functions

Sam Benry
Ranch Hand

Joined: Mar 21, 2008
Posts: 89
I want to create a function to do this:
"1"
"1 2 1"
"1 2 1 3 1 2 1"
"1 2 1 3 1 2 1 4 1 2 1 3 1 2 1"

this is the "Ruler" problem, but I cant figure out how to put it in a recursive function, I am new to recursion so any help is appreciated.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 40034
    
  28
Remember how a recursion works: a method (called a function in other languages) calls itself (usually directly, occasionally via another method).

For a recursion to work properly, it must terminate, which means two things:
  • There must be a "base case" where the recursion stops. The commonest base cases are stopping at value 1 and stopping at value 0.
  • The recursion must converge on the base case. The commonest way to do this is with i - 1.
  • Now go through what you have written, and write down on a sheet of paper how you get the very simplest case to work, then the next case.

    BTW: this recursion has exponential complexity, of O(2^n) where n is the depth of recursion.
    Joanne Neal
    Rancher

    Joined: Aug 05, 2005
    Posts: 3742
        
      16
    Originally posted by Campbell Ritchie:
    BTW: this recursion has exponential complexity, of O(2^n) where n is the depth of recursion.


    Do you mean that the recursive method will be called 2^n times ?
    If so, I think there's a simpler way to do it where the recursive method is called n times.


    Joanne
    Bill Shirley
    Ranch Hand

    Joined: Nov 08, 2007
    Posts: 457
    Campbell, I think this is an O(N) algorithm.

    Sam, can you state the N -> N+1 operation in English?

    (I.E. my first guess from step 0 to step 1 was: take the list of numbers, duplicate it, between the two lists, add the sum of the lists. Obviously, that didn't work for the next step. So,...)


    Bill Shirley - bshirley - frazerbilt.com
    if (Posts < 30) you.read( JavaRanchFAQ);
    Sam Benry
    Ranch Hand

    Joined: Mar 21, 2008
    Posts: 89
    what we are doing, is taking the string as it is, placing it, adding +1 to the heights number and putting it there, then putting the same string there agian
    1
    1 2 1

    121 3 121

    1213121 4 1213121
    Bill Shirley
    Ranch Hand

    Joined: Nov 08, 2007
    Posts: 457
    And will you state
    how many iterations/recursions to perform?
    how high to let the number get? (related)

    Is the initial value constrained, or can it be anything?

    Do you have to manipulate it as strings, or might you put it into a List<Integer> and manipulate it that way? Possibly returning the value to a string at the end.

    Note that, if initial values are constrained to the example (VALUE(0) = "1"), then the highest number is always in the middle of the String/List.


    starting spots...

    [ May 27, 2008: Message edited by: Bill Shirley ]
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 40034
        
      28
    I did it in about 5 lines of code in a single method, but my solution runs in exponential time; for dept = 5 it prints 31 numbers. I actually printed the numbers to screen rather than attaching them to a String.

    Once Ben has got his solution, I shall be very interested to see how you do it in linear time.
    amitabh mehra
    Ranch Hand

    Joined: Dec 05, 2006
    Posts: 98
    Campbell, does not the following code run with O(n) complexity and gives the desired output:

    Vikas Kapoor
    Ranch Hand

    Joined: Aug 16, 2007
    Posts: 1374
    Hello Amitabh,

    Didn't you read this anywhere in Java (beginner) forum?

    We're all here to learn, so when responding to others, please focus on helping them discover their own solutions, instead of simply providing answers.


    Please keep this in mind next time.
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 40034
        
      28
    Vishal, you are correct about not providing answers, but in this instance I shan't delete the solution.

    I think actually, Amitabh, you and I have both fallen for the trap of printing out the result, and Sam is supposed to return a String with the result in.
    You have also taken the step of adding to your index rather than subtracting. You ought to have something like if (i == 0) rather than if (i > depth).

    And a return statement in the middle of a method is often regarded as poor style.

    I haven't tried yet, but I think Bill Shirley (who always knows what he is talking about) is correct. It should be possible to write a class which implements this following interface, with an algorithm running in linear time.I think I know how to do it, but haven't tried yet.

    Sam: we expect you to produce an answer which is nice and neat and runs in linear time. You can probably get it down to 3 or 4 lines of code.
    Sam Benry
    Ranch Hand

    Joined: Mar 21, 2008
    Posts: 89
    how about this?


    I have one question that I found very weird, the program crashes completely if you changed

    to

    (currentValue is not incremented by one...)
    Joanne Neal
    Rancher

    Joined: Aug 05, 2005
    Posts: 3742
        
      16
    Originally posted by Sam Benry:
    how about this?

    to

    (currentValue is not incremented by one...)


    Try printing out the value of x after each of these statements.

    As to your program - if it does what you want then it's fine, but just as an exercise you might want to try implementing it the way Campbell suggested where you only need to pass one parameter to your recursive method.
    amitabh mehra
    Ranch Hand

    Joined: Dec 05, 2006
    Posts: 98
    are you having problem with post increment operator. Check this: post increment

    You would get OutOfMemoryError if your recursion goes into infinite.
    Joanne Neal
    Rancher

    Joined: Aug 05, 2005
    Posts: 3742
        
      16
    Actually, having looked at your code a bit more closely, it only prints out the last line and there are no spaces between the numbers, so I don't think it does do what you want.
    Joanne Neal
    Rancher

    Joined: Aug 05, 2005
    Posts: 3742
        
      16
    Originally posted by amitabh mehra:
    You would get OutOfMemoryError if your recursion goes into infinite.


    More likely to be a StackOverflowError
    amitabh mehra
    Ranch Hand

    Joined: Dec 05, 2006
    Posts: 98
    In this case, after running the code by Sam, i got the OutOfMemoryError.. may be because JVM could not find memory to allocate while creating new String in each recursion.
    Sam Benry
    Ranch Hand

    Joined: Mar 21, 2008
    Posts: 89
    spaces can be easily added to return statment and if you want to print each line you could either return a String[] having all the lines of print line inside the method, pretty easy to modify the code to make it do what you want.
    Joanne Neal
    Rancher

    Joined: Aug 05, 2005
    Posts: 3742
        
      16
    Originally posted by Sam Benry:
    spaces can be easily added to return statment and if you want to print each line you could either return a String[] having all the lines of print line inside the method, pretty easy to modify the code to make it do what you want.


    As long as you're happy with the result, that's what matters. I would just say there's an easier way to do it without having to store all the Strings or pass so many parameters, which might be a nice exercise.
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 40034
        
      28
    Agree, Joanne. And I have worked out how to get it to run on linear time, and return a String. Quite easy. One recursive method with a single int parameter and a single statement using ?:
    Bill Shirley
    Ranch Hand

    Joined: Nov 08, 2007
    Posts: 457
    I think the Big-O of the algorithm depends on what you are counting. You need to state what n is and what is the "cost" of performing the algorithm. Sometimes it's memory size, other times it's time (they're often related).

    When I initially stated that I thought it was O(n), I fell into a common trap. I was counting method invocations. n=depth and cost=method invocation. All the solutions are O(n) in that case.


    However, a more reasonable and useful (correct) measure is n=depth, cost=count of numbers generated.

    At this point, you are in danger of saying, you are doubling and adding one each time. But the number of numbers you are doubling is NOT n, it's an ever-increasing number.

    If you inspect the sequence lengths, you may (and you may not) be able to determine...



    count(1) = 1
    count(2) = 3
    count(3) = 7
    count(4) = 15
    ...
    count(n) = 2^n - 1

    thus the O(2^n) that Campbell initially posited,

    If you are generating a string, or if you are counting the cost of printing one number as "1", then that is the correct answer.
    -----------------

    but...

    notice that the 4th step above could be maintained in a tree form as follows:



    This could be optimized with each node pointing to two children that were the same...



    So, here the data structure would be O(n), but as with all binary trees, traversing it would still be O(2^n). It you were more worried about memory than time, then this could be an important solution.
    [ May 28, 2008: Message edited by: Bill Shirley ]
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Help with simple Recursive functions