# Recursion Problem

Dave DiRito

Ranch Hand

Posts: 77

posted 8 years ago

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

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

posted 8 years ago

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.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.

Dave DiRito

Ranch Hand

Posts: 77

posted 8 years ago

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.

Dave DiRito

Ranch Hand

Posts: 77

posted 8 years ago

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

Thanks for helping me, Paul,

Dave

Dave DiRito

Ranch Hand

Posts: 77

Dave DiRito

Ranch Hand

Posts: 77

Katrina Owen

Sheriff

Posts: 1367

18

posted 8 years ago

Hi Dave,

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

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!)

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

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

Ranch Hand

Posts: 77

posted 8 years ago

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.

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

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.

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

Ranch Hand

Posts: 77

posted 8 years ago

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.

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

Ranch Hand

Posts: 1296

posted 8 years ago

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?

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

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

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

Dave DiRito

Ranch Hand

Posts: 77

posted 8 years ago

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:

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

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:

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

Dave DiRito

Ranch Hand

Posts: 77

posted 8 years ago

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

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

Ranch Hand

Posts: 77

posted 8 years ago

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

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

Sheriff

Posts: 48981

60

posted 8 years ago

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

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

Ranch Hand

Posts: 77

posted 8 years ago

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

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

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

Sheriff

Posts: 48981

60

posted 8 years ago

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

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

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

Sheriff

Posts: 48981

60

Piet Verdriet

Ranch Hand

Posts: 266

Dave DiRito

Ranch Hand

Posts: 77

posted 8 years ago

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?

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

Ranch Hand

Posts: 266

posted 8 years ago

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

Note that there is a

[ April 22, 2008: Message edited by: 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

Sheriff

Posts: 48981

60

posted 8 years ago

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 thisIn 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

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 thisIn 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.

Garrett Rowe

Ranch Hand

Posts: 1296

posted 8 years ago
Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

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.

Can you see the recursion in that kind of algorithm?

Can you see the recursion in that kind of algorithm?

Campbell Ritchie

Sheriff

Posts: 48981

60

Dave DiRito

Ranch Hand

Posts: 77

posted 8 years ago

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

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

Ranch Hand

Posts: 77

posted 8 years ago

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?

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

Sheriff

Posts: 48981

60

Dave DiRito

Ranch Hand

Posts: 77

Dave DiRito

Ranch Hand

Posts: 77

Campbell Ritchie

Sheriff

Posts: 48981

60

posted 8 years ago

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:

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.

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:

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

Sheriff

Posts: 48981

60

Dave DiRito

Ranch Hand

Posts: 77

posted 8 years ago

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)

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

thankYou(thankYou)

posted 8 years ago

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?

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

So you have one or two more lines of code to write.I'll deal with negative integers after I get this working correctly.

Dave DiRito

Ranch Hand

Posts: 77

posted 8 years ago

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

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

Sheriff

Posts: 48981

60

Campbell Ritchie

Sheriff

Posts: 48981

60

Campbell Ritchie

Sheriff

Posts: 48981

60

posted 8 years ago

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

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.

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

Ranch Hand

Posts: 77

posted 8 years ago

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

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