• 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
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

problem with recursion

 
Ranch Hand
Posts: 4716
9
Scala Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
i am trying to solve project euler problem 76.
"How many different ways can one hundred be written as a sum of at least two positive integers?"
i tried a recursive approach but i get incorrect answers.
for 5 the answer should be 6. i get answer 7.
for 6 the answer should be 10. i get answer 9.
recursion has never been easy for me and i don't see what i am doing wrong.
this problem should ideally be solved using dynamic programming since the recursive solution will probably be slow, so any suggestions in that regard are welcome also. here is what i have.
 
Bartender
Posts: 4179
22
IntelliJ IDE Python Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Recursion and looping is a pretty heady topic to just walk through and figure out what is going wrong wrong. What I would do (were I you) would be:
1) start with a smaller number than 100
2) walk through the process by hand. Write each iteration so I can see how I got to the answer.
3) add print statements so I can see what is being counted in code. Or add break points and run in a debugger so I can look at different values as the code executes.
4) Compare #3 to #2 and see where the mistake is coming from
5) Scale up toe 100.
 
Randall Twede
Ranch Hand
Posts: 4716
9
Scala Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
that is how i am trying to figure it out. they gave me the answer for 5 and i found the answer for 6 by hand. i have been trying System.out.println but havent figured it out yet. i will keep trying.
 
Saloon Keeper
Posts: 15484
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Randall, recursion becomes much easier if your code is self-documenting. I wouldn't call recurse() a particularly descriptive method name. What problem does it solve?

What if you have a method int waysToWrite(int number, int limit)? It will determine in how many ways you can write number, with none of the terms of the sums exceeding limit. Let's take 7 as an example:

7
6 1
5 2
5 1 1
4 3
4 2 1
4 1 1 1
3 3 1
3 2 2
3 2 1 1
3 1 1 1 1
2 2 2 1
2 2 1 1 1
2 1 1 1 1 1
1 1 1 1 1 1 1


That gives the following number of ways to write 7, you just need to add them together:

7: 1
6: waysToWrite(1,6)
5: waysToWrite(2,5)
4: waysToWrite(3,4)
3: waysToWrite(4,3)
2: waysToWrite(5,2)
1: waysToWrite(6,1)



My implementation of waysToWrite() didn't use dynamic programming, and took about 10 seconds to come up with the answer for waysToWrite(100, 99). You can add a HashMap that stores answers you already computed in a previous run, which will probably cause the program to come up with the final answer instantaneously.
 
reply
    Bookmark Topic Watch Topic
  • New Topic