• Post Reply Bookmark Topic Watch Topic
  • New Topic

Tips for writing Recursive methods  RSS feed

 
P Derlyuk
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Jeanne Boyarsky
author & internet detective
Marshal
Posts: 37462
537
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks! Here is what I did and it seems to work.

 
Jeanne Boyarsky
author & internet detective
Marshal
Posts: 37462
537
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Never mind, I got it.
Thanks for the earlier help!
 
P Derlyuk
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here is what I did.

 
Campbell Ritchie
Marshal
Posts: 56529
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!