On Sat, Jan 4, 2020 at 10:37 AM Roelof Wobben via Pharo-users < pharo-users@lists.pharo.org> wrote:
> Oke, > > So I can better not use recursion for this problem if I understand you > well, Richard. > That is oversimplifying. If the purpose of the *training* *exercise* is to learn how to use recursion, then using recursion is a necessary thing. If the purpose of the exercise is to solve a problem, understanding whether there are more efficient approaches to the solution is an essential skill. This particular problem could have been solved using a recursive implementation, an iterative implementation, or a fundamental reframing of the problem to change it to an O(1) problem. Other problems are no so simply reframed. One of the most important skills you will ever develop is to understand that a request for a feature may not be accurately describing the problem. A feature request is often a description of a problem from a single perspective. Learning to recognize whether it is one or the other will be crucial to your long-term success as a programmer. > Roelof > > > > Op 4-1-2020 om 19:02 schreef Richard Sargent: > > On Sat, Jan 4, 2020 at 9:47 AM Roelof Wobben via Pharo-users < > pharo-users@lists.pharo.org> wrote: > >> Hello, >> >> For a exercism challenge I need to calculate the total grains on a >> chessboard. >> So I did : >> >> atSquare: anInteger >> self validateInput: anInteger. >> ^ anInteger = 1 >> ifTrue: [ 1 ] >> ifFalse: [ 2 * (self atSquare: anInteger - 1) ] >> >> >> but when I run the tests , the vm seems to be not responsive for some 4 >> - 5 seconds. >> >> Is there a way I can use this code and take care that the vm stays >> responsive. >> > > What do you want the VM to do in addition to calculating that sum while it > is calculating that sum? > > > The best way to keep the VM responsive is to take a page from Gauss' > notebook and pay attention to the numbers[1]. Let's consider the first four > squares and extrapolate from there. > > In binary, the squares hold the following grains: 2r1, 2r10, r2100, and > 2r1000. When we add them up, we get 2r1111. If we use Gauss' tricks, we can > notice that 2r1111 is equal to 2r10000 - 1. So, the sum of the grains on > the first 4 squares is 2^5 - 1. You can easily generalize that pattern, of > course. Then your program can calculate the answer quickly. > > > [1] The story goes that Gauss' teacher was frustrated with his student's > abilities and set him a challenge to occupy him for some time: sum the > numbers from 1 through 100. Gauss immediately answered 5,050, much to his > teacher's chagrin. > > >> Regards, >> >> Roelof >> >> >> >
