This week's book giveaway is in the OO, Patterns, UML and Refactoring forum. We're giving away four copies of Refactoring for Software Design Smells: Managing Technical Debt and have Girish Suryanarayana, Ganesh Samarthyam & Tushar Sharma on-line! See this thread for details.

The objective is the get the count of how many times a particular element exists in the tree. My code can find the count of elements in the leftmost children of the left subtree and the rightmost children in the right subtree, but not in the between. Therefore, I don't get to count other elements. Any hints as to how to solve this issue.

There are two cases to code, the base case and the recursive case. The base case happens for n = 1, and is straightforward. For the recursive case, you need to define how row "n" is defined in terms of row "n-1". In other words, if you know how to solve it for "n-1", how can you use that solution for "n"?

Now how do I set this up. any hints as to where to start in order to produce the above format of numbers.

Ulf Dittmer
Rancher

Joined: Mar 22, 2005
Posts: 42958

73

posted

0

numbers(n-1)

This implies that whatever is done for "n-1" is exactly the same as what's being done for "n", but that's not the case. For starters, the output for "n-1" is contained twice in the output for "n", not just once.

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 43975

33

posted

0

And many of us who like structured programming would prefer to see if . . . else rather than if . . . return.

Dubravko Zubavich
Greenhorn

Joined: Mar 04, 2009
Posts: 20

posted

0

Ulf Dittmer wrote:

numbers(n-1)

This implies that whatever is done for "n-1" is exactly the same as what's being done for "n", but that's not the case. For starters, the output for "n-1" is contained twice in the output for "n", not just once.

Is this what you mean...............

public static void numbers(int n)
{
if(n == 1)
System.out.println(n);

Sam Mercs wrote:Having a look at your pattern, I see it like this.

n = 1
Output : 1 (Trivial Case)

n = 2
Output : <Output of case n-1> 2 <Output of case n-1>
which turns out to be 1 2 1

n = 3
Output : <Output of case n-1> 3 <Output of case n-1>
which turns out to be <Output of case 2> 3 <Output of case 2> which is 1 2 1 3 1 2 1

This is the recursion pattern. Of course it's a pretty tough pattern - recursion has never been an easy thing to do.

I understand the pattern as you mentioned. But I cannot think of how to code this in recursive pattern. This is my first try at recursion and first programming class in Java.

I understand the pattern as you mentioned. But I cannot think of how to code this in recursive pattern. This is my first try at recursion and first programming class in Java.

Have you ever coded anything recursively at all?
If not you should give something a little easier a try first. Maybe these problems might help a bit...

Once you get the hang of recursion its pretty easy to write.

Dubravko Zubavich
Greenhorn

Joined: Mar 04, 2009
Posts: 20

posted

0

Sam Mercs wrote:

I understand the pattern as you mentioned. But I cannot think of how to code this in recursive pattern. This is my first try at recursion and first programming class in Java.

Have you ever coded anything recursively at all?
If not you should give something a little easier a try first. Maybe these problems might help a bit...

Once you get the hang of recursion its pretty easy to write.

I am very new to recursion and I have to turn the solution in by beginning of next week. Therefore, I am in sort of a panic mode. We didn't get much time to cover this topic and since its the end of term the course pace has accelerated.

I know I cannot ask for complete solutions but I need some major help here.

Dubravko Zubavich
Greenhorn

Joined: Mar 04, 2009
Posts: 20

posted

0

I have figured out the recursion problem. I can't believe it. Its almost magical.

But I still need to figure out the counting of elements in the tree.