From: Robert Dober <robert.dober@...>
Date: 2006-07-13T21:08:40+09:00
Subject: Re: Recursion and Ruby

------=_Part_6295_9432762.1152792516461
Content-Type: multipart/alternative; 
	boundary="----=_Part_6296_25308945.1152792516461"

------=_Part_6296_25308945.1152792516461
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

On 7/13/06, Dominik Bathon <dbatml@gmx.de> wrote:
>
> On Thu, 13 Jul 2006 10:57:29 +0200, Erik Veenstra <erikveen@gmail.com>
> wrote:
> [SNIP]



It might be of interest to the OP to examine the recursive calls in the
original method
after typo correction ;)

f(n) calss f(n-1) and f(n-2),
              f(n-1) calls f(n-2) and f(n-3)
                             f(n-2):        f(n-3) and f(n-4)
etc etc

In other words f(n-1) will redo almost all the work done in f(n-2)
In order to avoid this would it not be nice to have the result of f(n-2)
handy when computing f(n-1)?

I have attached an implementation of that and the not surprising performanc=
e
gain (we are going from O(2**n) to O(n) after all ;)
but did not paste it into the post so that OP can try to come up with
his/her own solution.

Cheers
Robert



--=20
Deux choses sont infinies : l'univers et la b=EAtise humaine ; en ce qui
concerne l'univers, je n'en ai pas acquis la certitude absolue.

- Albert Einstein

------=_Part_6296_25308945.1152792516461
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

<br><br><div><span class=3D"gmail_quote">On 7/13/06, <b class=3D"gmail_send=
ername">Dominik Bathon</b> &lt;<a href=3D"mailto:dbatml@gmx.de">dbatml@gmx.=
de</a>&gt; wrote:</span><blockquote class=3D"gmail_quote" style=3D"border-l=
eft: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left:=
 1ex;">
On Thu, 13 Jul 2006 10:57:29 +0200, Erik Veenstra &lt;<a href=3D"mailto:eri=
kveen@gmail.com">erikveen@gmail.com</a>&gt;<br>wrote:<br>[SNIP]</blockquote=
><div><br><br>It might be of interest to the OP to examine the recursive ca=
lls in the original method=20
<br>after typo correction ;)<br><br>f(n) calss f(n-1) and f(n-2),<br>&nbsp;=
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; f(=
n-1) calls f(n-2) and f(n-3)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&=
nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbs=
p;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; f(n-2):&nbsp;&nbsp;&nbsp=
;&nbsp;&nbsp;&nbsp;&nbsp; f(n-3) and f(n-4)<br>etc etc<br><br>In other word=
s f(n-1) will redo almost all the work done in f(n-2)
<br>In order to avoid this would it not be nice to have the result of f(n-2=
) handy when computing f(n-1)?<br><br>I have attached an implementation of =
that and the not surprising performance gain (we are going from O(2**n) to =
O(n) after all ;)
<br>but did not paste it into the post so that OP can try to come up with h=
is/her own solution.<br><br>Cheers<br>Robert<br></div><br></div><br clear=
=3D"all"><br>-- <br>Deux choses sont infinies : l'univers et la b=EAtise hu=
maine ; en ce qui concerne l'univers, je n'en ai pas acquis la certitude ab=
solue.
<br><br>- Albert Einstein

------=_Part_6296_25308945.1152792516461--

------=_Part_6295_9432762.1152792516461
Content-Type: application/x-ruby; name=fibo.rb
Content-Transfer-Encoding: base64
X-Attachment-Id: f_epl3agwn
Content-Disposition: attachment; filename="fibo.rb"

IyEvdXNyL2Jpbi9lbnYgcnVieQpyZXF1aXJlICdiZW5jaG1hcmsnCgpkZWYgZmliICggbiApCglj
YXNlIG4KCQl3aGVuIDAsIDEKCQkJMQoJCWVsc2UKCQkJZmliKCBuIC0gMSApICsgZmliKCBuIC0g
MiApCgllbmQKZW5kCgpkZWYgZmliMiggbiApCgljYXNlIG4KCQl3aGVuIDAKCQkJWzEsIDBdICMg
cmV0dXJuIFtmKG4rMSksIGYobildCgkJZWxzZQoJCQl4ID0gZmliMiggbiAtIDEgKSAjICBbZihu
KSwgZihuLTEpXQoJCQlbIHguZmlyc3QgKyB4Lmxhc3QsIHguZmlyc3QgXQoJZW5kCmVuZAogCm4g
PSAzMApCZW5jaG1hcmsuYm0gZG8KICAgICAgICB8Ym18CiAgICAgICAgYm0ucmVwb3J0ICJmaWIi
IGRvCiAgICAgICAgICAgICAgICBuLnRpbWVzIGRvCgkJCXxrfAoJCQlwdXRzICJmKCAiIDw8IGsu
dG9fcyA8PCAiKSA9ICIgPDwgZmliKGspLnRvX3MKICAgICAgICAgICAgICAgIGVuZAogICAgICAg
IGVuZCAjIGRvCgogICAgICAgYm0ucmVwb3J0ICJmaWIyIiBkbwogICAgICAgICAgICAgICAgbi50
aW1lcyBkbwoJCQl8a3wKCQkJcHV0cyAiZiggIiA8PCBrLnRvX3MgPDwgIikgPSAiIDw8IGZpYjIo
aykuZmlyc3QudG9fcwogICAgICAgICAgICAgICAgZW5kCiAgICAgICAgZW5kICMgZG8KZW5kCg==

------=_Part_6295_9432762.1152792516461--