This week's book giveaway is in the Design forum.
We're giving away four copies of Experimentation for Engineers: From A/B testing to Bayesian optimization and have David Sweet on-line!
See this thread for details.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
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
  • Ron McLeod
  • Tim Cooke
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • Junilu Lacar
  • Rob Spoor
  • Jeanne Boyarsky
Saloon Keepers:
  • Stephan van Hulst
  • Carey Brown
  • Tim Holloway
  • Piet Souris
Bartenders:

Tips for writing Recursive methods

 
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
author & internet detective
Posts: 41586
883
Eclipse IDE VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks! Here is what I did and it seems to work.

 
Jeanne Boyarsky
author & internet detective
Posts: 41586
883
Eclipse IDE VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here is what I did.

 
Marshal
Posts: 77566
372
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
     
    Switching from electric heat to a rocket mass heater reduces your carbon footprint as much as parking 7 cars. Tiny ad:
    The Low Tech Laboratory Movie Kickstarter is LIVE NOW!
    https://www.kickstarter.com/projects/paulwheaton/low-tech
    reply
      Bookmark Topic Watch Topic
    • New Topic