programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Help with simple Recursive functions

Sam Benry
Ranch Hand
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
Marshal
Posts: 56546
172
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
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.

Bill Shirley
Ranch Hand
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,...)

Sam Benry
Ranch Hand
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
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
Marshal
Posts: 56546
172
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
Posts: 98
Campbell, does not the following code run with O(n) complexity and gives the desired output:

Vikas Kapoor
Ranch Hand
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
Marshal
Posts: 56546
172
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
Posts: 89

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
Posts: 3742
16
Originally posted by Sam Benry:

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
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
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
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
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
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
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
Marshal
Posts: 56546
172
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
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 ]