Recursion Problem

[Dave DiRito]

I need to write a recursive method that accepts an integer as a parameter and returns the integer obtained by replacing every digit of n with two of that digit. So, doubleDigits(276) would return 227766. If a negative number is passed to it, say -893, then it should return -889933.

It seems that it would be fairly easy to do it if I could convert the number to a string, but it must be a recursive method that accepts and returns an iteger. So, I believe it must be done mathmatically and that's where I'm stuck.

I can get the ones digit to double by using i = i*10 + i%10;
I don't know how to proceed from there. Any suggestions would be appreciated.

Thanks,
Dave

[Paul Clapham]

Originally posted by Dave DiRito:
I can get the ones digit to double by using i = i*10 + i%10;
I don't know how to proceed from there.

So far, so good. But it would be better to split the number into the ones digit and the rest. You know how to deal with the ones digit. Deal with the rest recursively. Then figure out how to put the two pieces together again.

[Dave DiRito]

OK, I've been trying to follow Paul Clapham's advice as well as trying other things and I'm just not getting it. I just don't know how to split the one's off from the rest, deal with the one's, do the rest recursively and then put them back together again to get the result I need.

[Paul Clapham]

You have the number 25147. Using simple arithmetic operations (hint: the ones you already posted), how do you get 7 and 2514?

[Dave DiRito]

OK, if I do the number mod 10, then the result of the division is the first part of the number and the mod is the ones. So, that's how I split them! Can't believe I didn't recognize that. So now I'm thinking I need two variables - one for each part. Am I right so far?

Thanks for helping me, Paul,
Dave

[Paul Clapham]

So far, so good!

[Dave DiRito]

Ok, so I can keep splitting off the last digit until there are no more, which is the recursion part, I believe. I don't know how I would code that, though.

[Dave DiRito]

I now have two variables called ones and remainder. How do you set it up to cycle through the number and then put it back together again with each digit doubled?

[Katrina Owen]

Hi Dave,

Basically you pass the remainder into the function you are already in.

public void recursiveFunction( int i )
{
    if ( endCondition )
    {
        // the buck stops here
    }
    else
    {
        // do stuff
        recursiveFunction( remainder );
    }
}

That is pseudo-pseudo code - won't compile, won't run, not tested, and not verified for correctness Just trying to show you what calling your function inside your function looks like.

You'll have to add the proper 'return' statements and assign stuff where it belongs.

(hm... I hope I didn't just make it worse with that explanation!)

[Dave DiRito]

Thanks, Katrina. That did help. I decided to change the name of my remainder variable to quotient to avoid confusion. I was using remainder to mean the part of the integer that remains after dividing by 10, but then I realized that part of division is called the quotient. Remainder actually refers to what's left over, which in my code I left as ones.

Anyway, here's as close as I got so far when I pass it a positive integer. I'll deal with negative integers after I get this working correctly.

if(i > 0){
    ones = i%10;
    System.out.println("ones = " + ones);
    quotient = i/10;
    System.out.println("quotient = " + quotient);
    result = (ones*10) + ones;
    System.out.println("result = " + result);
    doubleDigits(quotient);
    System.out.print(result);
}    

This code produces the following results if I pass it the number 147 for example:

ones = 7
quotient = 14
result = 77
ones = 4
quotient = 1
result = 44
ones = 1
quotient = 0
result = 11
0114477

As you can see, it's great except for that 0 in front. I believe what's causing it is that I'm calling the method when quotient = 0. I have tried a million things to fix it and nothing works. I would greatly appreciate any suggestions anyone has to help me figure out how to fix it.

Thanks,
Dave

[Dave DiRito]

Looking at Katrina's psuedocode and comparing to my code I see that I do not have an end condition to stop the recursion at the appropriate place. I can't figure out what the end condition should be. I keep thinking it's when the quotient equals zero because that's when there's no more number left to split up. Also, I'm not sure when should happen when the end condition is reached.

Since I cannot figure out these two things, I'm using the trial and error approach. I either get an infinite loop or an incorrect result.

Still hoping someone will take pity and give me some clue that will help enlighten me.

[Garrett Rowe]

I can't think of a way to do it cleanly without the recursive method taking an extra parameter that indicates a power of ten to multiply the result by. Can your method call a helper method?

public int doubleDigits(int num)
{
   return doubleDigits(num, 0);
}
 
public int doubleDigits(int num, int powOfTen)
{
   //base case
 
   //algorithmic stuff
 
   return localResult + doubleDigits(smallerNum, powOfTen + 1);
}

[ April 20, 2008: Message edited by: Garrett Rowe ]

[Dave DiRito]

Garrett, thanks for the suggestion. I don't think a helper method would be permitted as a solution, though. I keep thinking there is some piece I'm missing that has to do with putting the number back together again with the digits doubled that involves "unwinding" part of the recursion after it reaches the stop point.

I can make it look like it's producing the correct result with a System.out.print(result); statement, but if I make it a println statement or make it a method that returns a value, it reveals that I really haven't created an integer with all the digits doubled.

Here is my code as it exists right now along with the results it produces. The negative number condition doesn't work either, but I'm not worried about that until I get the positive number condition working properly first:

if(i == 0){
    System.out.println(result);
}else if(i > 0){
    quotient = i/10;
    System.out.println("quotient = " + quotient);
    ones = i%10;
    System.out.println("ones = " + ones);
    result = (ones*10) + ones;
    System.out.println("result before dd = " + result);    
    doubleDigits(quotient);
    System.out.print(result);
}else{
    quotient = i/10;
    System.out.println("quotient = " + quotient); [quote]    [/quote]
    ones = i%10;
    System.out.println("ones = " + ones);
    result = (ones*10) + ones;
    System.out.println("result before dd = " + result);
    doubleDigits(quotient);
}    

Enter a number for Double Digits: 147

quotient = 14
ones = 7
result before dd = 77
quotient = 1
ones = 4
result before dd = 44
quotient = 0
ones = 1
result before dd = 11
-1
114477

[Paul Clapham]

So: you start with 147. You split that into 14 and 7. You make the 7 into 77 and call something recursively to make the 14 into 1144. Now your task is to combine 1144 and 77 to make 114477... you can't figure out how to do that with arithmetic?

[Dave DiRito]

Paul, I greatly appreciate your help with this. Thank you!

I believe what you're telling me is that I need a statement somewhere that puts the pieces back together again. I think it may be something like:
result = result*100 + result;

I think I am also missing the stop condition as Katrina indicated in her psuedocode. I think that it should do the recursion part of taking the number apart by stripping the ones off the end, turning them into doubles (so 7 becomes 77) until it reaches the stop point (I think that should be when quotient == 0). From there it should go back through the stack of method calls and put the number back together with each digit doubled.

Is that how it should work?

Thank you again for your help,
Dave

[Dave DiRito]

Ok, I can make 14 into 1144 when the quotient is at 1 and the ones is at 4 by doing:
num = quotient*1000 + quotient*100 + ones*10 + ones
1144 = 1*1000 + 1*100 + 4*10 + 4

I think I need something similar to that, or maybe exactly that, to make 1144 into 114477. I'm not sure if this is correct. Even if it is correct I don't know where or how to fit that in to make it work recursively.

Am I on the right track at all?

Dave

[Campbell Ritchie]

You mean 147 to 114477.
You need to work out a base case, which is when you stop; using an argument of 0 is a good place to try.

You are more-or-less on the right lines with 10*ones+ones. But try 11*ones. And try adding the ones first. See whether you can see a recursion from that!

[Dave DiRito]

Thanks, Campbell.

OK, going back to basics, I see that I can turn 147 into 114477 by doing:
114477 = (7 + 7*10) + (4 + 4*1000) + (1 + 1*10000)

I know how to break apart 147 into each part 7, 4, and 1, to get the numbers I need for the equation above. I just can't figure out how to put this all together into recursive code to get the final number 114477.

I realize I need a base case and I kept trying quotient == 0. That didn't work until I set quotient equal to the original number at the very top of the method. I still don't know what should happen when quotient gets to 0.

Here's my code right now followed by the output it produces. I replaced the variable name quotient with q and I am not yet sending it any negative numbers.

Thanks,
Dave

    public static void doubleDigits(int i){
int ones, result = 0, q = i, num = 0;
if(i == 0){
    System.out.println(i);
}
if(q == 0){
    System.out.println("q at 0, num at " + num);
}else if(i > 0){
    q = q/10;
    System.out.println("q = " + q);
    ones = i%10;
    System.out.println("ones = " + ones);
    result = ones + (10*ones);
    System.out.println("result before call = " + result);    
    doubleDigits(q);
    num = q*1000 + q*100 + result;
    num = result;
    System.out.println("num = " + num);
}else{
    q = i/10;
    System.out.println("q = " + q);
    ones = i%10;
    System.out.println("ones = " + ones);
    result = (ones*10) + ones;
    System.out.println("result before dd = " + result);
    doubleDigits(q);
}    

Enter a number for Double Digits: 147

q = 14
ones = 7
result before call = 77
q = 1
ones = 4
result before call = 44
q = 0
ones = 1
result before call = 11
0
q at 0, num at 0
num = 11
num = 44
num = 77

[Campbell Ritchie]

You are getting closer, but (even when you ignore the println calls) your result looks very complicated.
Remember what you are trying to do is make 147 into 114477 by adding 0+77+4400+110000 or by adding 110000+4400+77+0. I have already hinted which I think would be easier to implement.
Remember you can make 7 into 77 by multiplying by 11. Or you can make 4 into 4400 by multiplying by 11 then multiplying by 100.

Is there a difference between your if (q > 0) block and else if (q < 0) block? I don't think there is, but you may get into confusion because the statements are in different orders. If there is no difference, then do you need both blocks at all?

And has nobody told you to avoid void methods for recursion? You are trying to get your int into an int, so you will need a return type.

Work out how to turn 0 into 0
Work out how to turn 7 into 77
etc
etc

[Campbell Ritchie]

As for void methods, you said in your first post that you are supposed to take an integer and return an integer. So that means you shouldn't have a void return type.

[Piet Verdriet]

Here's some pseudo code:

doubleDigits(456)
  n = 456
    logTenFloored = floor[log10(n)] = 2
    leftDigit = n / 10^logTenFloored = 4
    partialSum = leftDigit * (10^(2*logTenFloored) + 10^(2*logTenFloored+1)) = 440000
    newN = n - (leftDigit * 10^logTenFloored) = 56
      recursive call ...

[ April 22, 2008: Message edited by: Piet Verdriet ]

[Dave DiRito]

Sorry to be so dense about this. I greatly appreciate everyone's help walking me through it.

From Garrett's post I see the pattern that to turn the ones into double digits you multiply it by 11, the tens digit becomes a ten thousand number by multiplying by 1100, the hundreds digit becomes a hundred thousand number by multiplying by 110,000. So, I must need some kind of log function like Piet just posted or something to raise 11 to some power of 10 based on the size of the number that's passed into the method. Is that what I need?

[Piet Verdriet]

Originally posted by Dave DiRito:
Sorry to be so dense about this. I greatly appreciate everyone's help walking me through it.

From Garrett's post I see the pattern that to turn the ones into double digits you multiply it by 11, the tens digit becomes a ten thousand number by multiplying by 1100, the hundreds digit becomes a hundred thousand number by multiplying by 110,000. So, I must need some kind of log function like Piet just posted or something to raise 11 to some power of 10 based on the size of the number that's passed into the method. Is that what I need?

There are two ways to solve this: going from right to left, in which case you need an extra parameter to keep track of how much you need to multiply the number (the powOfTen parameter from Garrett's post), or from left to right, in which case you don't need an extra argument because the logTenFloored variable will be sufficient to calculate the "double digits".

Note that there is a log10(...) method in the java.lang.Math class, you don't need to implement that yourself. And the floor[...] part can simply be implemented by casting the double to an int.
[ April 22, 2008: Message edited by: Piet Verdriet ]

[Campbell Ritchie]

You don't need logs, or counts of digits. All this talk of logs is simply confusing you even more.

You can do everything with the five standard arithmetic operators. And you don't even need all 5. You can get it down to a single method and the resulting code will be really short and simple. Your method will take an int parameter and return an int: that was mentioned as a requirement in your very first posting. Then you write a method like this

public void doubleAndPrint(int i)
{
   System.out.printf("If you double the digits in %d you get %d%n%n", i, doubleDigits(i));
}//end double and print
 
public int doubleDigits(int i)
{
   // You didn't expect me to give the answer, did you?
}//end double digits

In my opinion, both those methods should be static. You will get the wrong answer if |i| > 19999 because of an overflow error.

Start from scratch.

You start with a number like 147.

You want to get 114477.

If you start with a number like 0 you want to get 0.

You want to turn 7 into 77.

You then have to do something with the 14.

Now try something simple which can give 0 from 0.

Now turn 7 into 77.

Now think about how to put the whole lot back together

[Garrett Rowe]

I agree with Campbell. Paul had you going in the right direction, but you abandoned ship. Please ignore my previous post, as it will only serve to confuse the issue.

start with 147
  split into 14, 7
  make the 7 into 77
--make the 14 into 1144
| combine 1144 and 77 to make 114477
|
|start with 14
   split into 1 and 4
   make the 4 into 44
---make the 1 into 11
|  combine 11 and 44 to make 1144
|
|-start with 1
   split into 0, 1
   make the 1 into 11
   make the 0 into 0
   combine 0 and 11 to make 11

Can you see the recursion in that kind of algorithm?

[Campbell Ritchie]

Originally posted by Garrett Rowe:
Can you see the recursion in that kind of algorithm?

If you find it difficult, read Garrett Rowe's last post backwards. Recursion may be easier to understand backwards.

[Dave DiRito]

Thank you, Campbell and Garrett. I really want to get this and I appreciate you hanging in and helping me.

I am working on it right now, Campbell. I have taken your advice and made the method return an int, as required, and tried to simplify it. Currently, it works for 0 and single digit numbers only. For numbers greater than 10, it breaks off each digit and turns it into doubles but does not combine them back together into the final produce. That's what I'm missing and I think that's the part that needs recursion to work properly.

Thank you again,
Dave

[Dave DiRito]

Ok, I see a pattern:

ones*11*10 to the 0 power doubles the ones digit.
ones(in the next pass will be the tens digit in the original number, if it has a tens digit)*11*10 to the 2nd power doubles the tens digit.
ones(in the third pass will be the hundreds digit in the original number, if it has a hundreds digit)*11*10 to the 4th power doubles the hundreds digit.
etc...

Is this getting closer?

[Campbell Ritchie]

Yes, you are getting closer, much closer.

But don't mess around with 10000 or 1000000 or 100000000. If you multiply by 100 several times that will take care of all those numbers. Please show us what you have got so far.

[Dave DiRito]

Thanks for the encouragement, Campbell. I was growing very weary. I haven't banged my head against something this much in a long time.
This code works correctly for 0 and any single digit number:

    public static int doubleDigits(int i){
int ones = 0, result = 0, q = i, num = 0;
if(q == 0){    
    return q;
}else{
    q = i/10;
    ones = i%10;
    result = ones*11;
    doubleDigits(q);
    //System.out.println("q = " + q);
    //System.out.println("ones = " + ones);
    //System.out.println("result before call = " + result);    
}
return result;
    }    

[Dave DiRito]

This seems to be slightly closer. It still works for 0 and single digit numbers and it tacks the single digit numbers after they're doubled onto the larger numbers. It just doesn't go through the recursion to continue the process for the larger numbers.

public static int doubleDigits(int i){
int ones = 0, result = 0, q = i, num = 0;
if(q == 0){    
    return result;
}else{
    q = i/10;
    ones = i%10;
    doubleDigits(q);
    result = 100*q + ones*11;
}
return result;
    }   

[Campbell Ritchie]

You are lot closer. You have the recursive call to doubleDigits(q), but you can call it more easily as doubleDigits(i/10), so you don't need q.

You have the call to multiply ones by 11, but you can lose the ones local variable and say i % 10 * 11 (make sure you get the arithmetic in that order; 11 * i % 10 will give a totally different result).

You don't use the num local variable, so you can lose that too.

You are correctly adding 100 * something to ones * 11.

Only you are adding the wrong something.

Try this:

public static int doubleDigits(int i)
{
   int result = 0;
   if(i != 0)
   {
      result = 100 * ??? + i % 10 * 11;
   }//end if
   return result;
}//end double digits.

I haven't given you the answer; I have simply copied what you wrote and simplified it. The bit about if(i != 0) means that if i IS 0 then the result remains at 0, otherwise it becomes something different.

Now: All you have to do is work out what to write in place of the ???

Hint: It is a simplification of something you have already written. I have dropped another hint very recently.

[Campbell Ritchie]

You can tell you are getting closer by how much shorter and simpler and neater your code is becoming.

[Dave DiRito]

Campbell, thank you, thank you so much for hanging in there with me. If it wasn't for your hints and encouragement along the way, I would have never gotten this. It has literally brought me to tears of joy and loud wooping sounds

The code is so elegant it's beautiful and I believe I actually understand it.
thankYou(thankYou)

    public static int doubleDigits(int i){
int result = 0;
if(i != 0){
    result = 100*doubleDigits(i/10) + i%10*11;
}    
return result;
    }    

[Paul Clapham]

Excellent! That's just like the code I would have come up with! (Which means it's good, of course.)

Just one thing, though... Remember back on April 19 you said this?

I'll deal with negative integers after I get this working correctly.

So you have one or two more lines of code to write.

[Dave DiRito]

Paul, actually it works just fine as is. The spec for it was that ff a negative number is passed to it, say -893, then it should return -889933. That's exactly what it does! I believe that's because the last step always involves multiplying a positive number by a negative one.

I owe you a great big thank you, too!
You started me off in the right direction and kept me on course in the early going. So an infinitely recursive thankYou(thankYou) to you, too.

Dave

[Campbell Ritchie]

Yes, you've got it. I waited until 11.45pm hoping to see you post a correct solution, then got too tired, and you got the answer a few minutes later. Well done.

[Campbell Ritchie]

BTW: Here's a solution which will work for negative numbers:

public static int doubleDigits(int i){
int result = 0;
if(i != 0){
    result = 100*doubleDigits(i/10) + i%10*11;
}    
return result;
    }

Challenge: use the ? : operator to reduce your solution to a single line. It's not difficult.
Challenge: Write out a likely stack for the calls to the recursive method and what it returns.

[Campbell Ritchie]

All right, here's how I would do it with the ?: operator:

public static int doubleDigits(int i)
{
   return i == 0 ? 0 : i % 10 * 11 + 100 * doubleDigits(i / 10);
}//end double digits

and this is some idea of what a call stack would look like

println(int)
doubleDigits(147)--->114477
doubleDigits(14)--->1144
doubleDigits(1)--->11
doubleDigits(0)--->0

You get a stack something like this. This is by no means hard-and-fast, or especially accurate, just a rough guess.
i //147
10
rem
11
mul
call doubleDigits
i
10
div
i //14
10
rem
11
mul
call doubleDigits
i
10
div
i //1
10
rem
11
mul
call doubleDigits
i
10
div
i //0
add
add
add
add
//at this point there is nothing else to put on the stack, so it unwinds.

[Dave DiRito]

Campbell, apparently our time zones are several hours apart as I am only just now seeing your posts (5:30 AM, 4/24).

Yes, the code does work for negative numbers I believe because it's always multiplying a negative number by a positive as it goes through the recursive cycle.

Using the ? : notation makes it even more elegant. Am I correct in reading it as "If i equals 0, then return 0, else do the recursion loop"?

I am not familiar with the call stack notation you posted, so I can't really interpret it. Thanks to working through this problem with your and Paul's help especially, I do have a better understanding of recursion.

I understand that each method call stacks up on the one before until it reaches the stop point (in this case when i == 0). Then it unwinds by returning it's value (result, in this case) to the one previous to it in the stack until it gets down to the first one which returns it's value to wherever it was called from in the first place (in my program, that would be the main method).

Is that a correct understanding of it?

Dave