programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Jeanne Boyarsky
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Rob Spoor
• Devaka Cooray
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Frits Walraven
• Tim Moores
Bartenders:
• Mikalai Zaikin

# Tips for writing Recursive methods

Ranch Hand
Posts: 33
• Number of slices to send:
Optional 'thank-you' note:
Does anyone have any good tips when writing recursive methods? For example, I am having trouble with this following method and maybe a push in the right direction would help a lot.
Thanks!

Write a method writeSequence that accepts an integer n as a parameter and prints a symmetric sequence of n numbers with descending integers ending in 1 followed by ascending integers beginning with 1, as in the table below:
Call Output
writeSequence(1); 1
writeSequence(2); 1 1
writeSequence(3); 2 1 2
writeSequence(4); 2 1 1 2

This method should throw an IllegalArgumentException if passed a value less than 1

author & internet detective
Posts: 41878
909
• Number of slices to send:
Optional 'thank-you' note:
When working on recursion, you think about the base case(s) and recursive case.

Can you write an implementation for writeSequence(1) and writeSequence(2) without using any recursion? Once you've done that, can you think about how to do writeSequence(3) calling one of those? How about writeSequence(4)?

P Derlyuk
Ranch Hand
Posts: 33
• Number of slices to send:
Optional 'thank-you' note:
So the even numbers will use the (n==2) base case while the odd will use (n==1) base case.

P Derlyuk
Ranch Hand
Posts: 33
• Number of slices to send:
Optional 'thank-you' note:
Thanks! Here is what I did and it seems to work.

Jeanne Boyarsky
author & internet detective
Posts: 41878
909
• Number of slices to send:
Optional 'thank-you' note:
Looks good! You might hard code what you output for the base cases to make it a bit easier to read

P Derlyuk
Ranch Hand
Posts: 33
• Number of slices to send:
Optional 'thank-you' note:
Could you possibly help with this method?

Write a recursive method digitMatch that accepts two non-negative integers as parameters and that returns the number of digits that match between them. Two digits match if they are equal and have the same position relative to the end of the number (i.e. starting with the ones digit). In other words, the method should compare the last digits of each number, the second-to-last digits of each number, the third-to-last digits of each number, and so forth, counting how many pairs match. For example, for the call of digitMatch(1072503891, 62530841), the method would compare as follows:

1 0 7 2 5 0 3 8 9 1
| | | | | | | |
6 2 5 3 0 8 4 1

The method should return 4 in this case because 4 of these pairs match (2-2, 5-5, 8-8, and 1-1). Below are more examples:
Call - Value Returned
digitMatch(38, 34) -1

Here is what I have so far and a I don't know why I keep getting a
Java.lang.StackOverflowError
at java.lang.Integer.toString(Integer.java:332)
at digitMatch (Line 5)
at digitMatch (Line 8)

P Derlyuk
Ranch Hand
Posts: 33
• Number of slices to send:
Optional 'thank-you' note:
Never mind, I got it.
Thanks for the earlier help!

P Derlyuk
Ranch Hand
Posts: 33
• Number of slices to send:
Optional 'thank-you' note:
Here is what I did.

Marshal
Posts: 79261
377
• Number of slices to send:
Optional 'thank-you' note:

P Derlyuk wrote:So the even numbers will use the (n==2) base case while the odd will use (n==1) base case.

Probably better to work out what you would return when i == 0 or i < 0. Use 0 as the base case, rather than 2, if possible.

Bartender
Posts: 10780
71
• Number of slices to send:
Optional 'thank-you' note:

P Derlyuk wrote:Does anyone have any good tips when writing recursive methods?

Yes: DON'T.

Actually, that's a bit over the top, but it's not a bad base to work from:
• Unless you have a good mathematics background, most of us find recursive logic quite difficult to follow; so if there's a simple way of solving the problem without recursion, it's probably better to use it.
• Any recursive method can be "unrolled" - and one test of how good a recursive solution is is how bad it looks when it is unrolled .

• My general rule of thumb is that if recursion provides a logarithmic solution (ie, the maximum "depth" of calls required is logₓ(n)), then it's probably the best way to go. It's also quite good for things like path or tree traversals since it isolates the logic to "what do I do now?", allowing you to forget about the rest of the structure (to some extent).

HIH

Winston