Tips for writing Recursive methods

[P Derlyuk]

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]

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]

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

[P Derlyuk]

Thanks! Here is what I did and it seems to work.

public void writeSequence(int n){
    if( n < 1){
        throw new IllegalArgumentException();
    }
    if(n==1){
        System.out.print(n);
    }
    else if(n==2){
        System.out.print(n/2 +" " + n/2);
    }
    else if(n%2 ==0){
        System.out.print(n/2 +" ");
        writeSequence(n-2);
        System.out.print(" " +n/2);
    }
    else if(n%2 ==1){
        System.out.print( (n/2+1) +" ");
        writeSequence(n-2);
        System.out.print( " "+(n/2 +1));
    }
}

[Jeanne Boyarsky]

Looks good! You might hard code what you output for the base cases to make it a bit easier to read

[P Derlyuk]

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)

public int digitMatch(int num1, int num2){
    if(num1 < 0 || num2 < 0){
        throw new IllegalArgumentException();
    }
    String s1 =Integer.toString(num1);
    String s2 = Integer.toString(num2);
    if( s1.charAt(s1.length()-1) == s2.charAt(s2.length() -1)){
        return 1 + digitMatch(num1 % 10, num2 % 10);
    }
    return 0 + digitMatch(num1 % 10, num2 % 10);
    
}

[P Derlyuk]

Never mind, I got it.
Thanks for the earlier help!

[P Derlyuk]

Here is what I did.

public int digitMatch(int x, int y){
    if(x < 0 || y < 0){
      throw new IllegalArgumentException();
    }
      else if(x < 10 || y < 10){
         if(x % 10 == y % 10)
            return 1;
         else
             return 0;
      } else if( x % 10 == y % 10){
         return 1 + digitMatch(x/10, y/10);
      }
    else{
         return digitMatch(x/10,y/10);
    }

[Campbell Ritchie]

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]

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