Why is recursion so much slower than “brute force”? The example is Fibonacci numbers in which the first two are 1 and all subsequent values are the sum of the previous two values. In the script below the ratio is about 500 to one and grows with the size of n!
to getFib(n)
if n = 0 or n = 1 then
return 1
else
set fib to {1, 1}
repeat with k from 3 to n
tell fib to set end to (item (k - 2)) + (item (k - 1))
end repeat
return end of fib
end if
end getFib
to getFibR(n)
if n = 0 or n = 1 then
return 1
else
return (getFibR(n - 1) + getFibR(n - 2))
end if
end getFibR
set {tt1, tt2} to {0, 0}
set f to 25
repeat 10 times
set t1 to GetMilliSec
getFibR(f)
set t2 to GetMilliSec
getFib(f)
set t3 to GetMilliSec
set {tt1, tt2} to {tt1 + t2 - t1, tt2 + t3 - t2}
end repeat
display dialog "Brute force: " & tt2 & return & "Recursive: " & tt1 & return & "Ratio: " & tt1 / tt2
Firstly, recursion is usually slower than repeating anyway, because of the passing of parameters, the storing and retrieval of stuff to and from the stack, and the two-way journey.
Secondly, your recursion handler checks n = 0 and n = 1 at every recursion and spawns two sets of recursions at every recursion except the last one, increasing the amount of work done exponentially. (By the way, it gives different results from the brute force handler. return 1 should be return n.)
Here’s another version. Not as compact as kai’s, but possibly a whisker faster and only requiring one initial parameter.
Edit: Actually, it’s slower than kai’s this afternoon. :rolleyes: But it still only needs one parameter. See my later post below.
to getFibR(n)
if (class of n is script) then
if (n's n > 2) then
set n's n to (n's n) - 1
getFibR(n)
set x to n's curr
set n's curr to x + (n's prev)
set n's prev to x
else
set n's n to (n's n) + 1
end if
else if (n > 2) then
script o
property n : missing value
property prev : 1
property curr : 1
end script
set o's n to n - 1
getFibR(o)
return (o's prev) + (o's curr)
else
return 1
end if
end getFibR
Both, of course were “brute force” constructed by a sleepy person :/. I was reading an article on Python that used the recursion example largely as I had ported it to AppleScript, and was indeed aware that I didn’t have to put together a complete series to get the last value - I was just blown away when the recursive version seemed to take so much longer. (I actually want the ‘full’ series: they can construct a Pascal’s triangle, and the elements of those are the coefficients of polynomials arising from (x + y)^n
Lessons from your and Nigel’s versions: if you’re going to use recursion, it had better be structured intelligently for AppleScript (or perhaps ‘structured intelligently’ is sufficient). Your solutions reduce the ratio to circa 1.5 - more like what I would have expected.
I suppose another lesson is that this problem isn’t really suitable for recursion. kai’s repeat version seems to be the best way in AppleScript to calculate the nth number in the Fibonacci sequence.
Also, my apologies to kai. The recursive handler I posted above isn’t faster than his “ not this afternoon, at any rate. One way to allow his handler to take only one parameter would be to put the recursive part in a script object within the handler:
to getFibR(r)
script o
to gfr(r, p, c)
if r < 3 then return c
gfr(r - 1, c, p + c)
end gfr
end script
return o's gfr(r, 1, 1)
end getFibR
getFibR(25) --> 75025
Often times a direct (repeated or calculated) answer is faster than a recursive one. The advantage to a recursive solution is often that it uses less code (and therefore appears more “elegant”).
I’ve found, though, that the value of recursion varies with the implementation of the language you’re working in. I wrote a lovely version of Tower of Hanoi in AS Studio that breaks if you try to run the automated play feature on an 8-piece stack. Apparently it’s an Applescript stack overflow.
That said, I found from running timings on Nigel and Adam’s quicksort routines (see this discussion in Code Exchange) that how you construct code in Applescript makes a HUGE difference in execution time.
Agree that Kai’s repeat version of the code is the way to go, and it gets me the whole series too:
to getFibSeries(r)
set {p, fibSeries, c} to {1, {1}, 1}
repeat r - 2 times
tell p + c
set p to c
set {c, end of fibSeries} to {it, it}
end tell
end repeat
return fibSeries
end getFibSeries
getFibSeries(10)
--> {1, 2, 3, 5, 8, 13, 21, 34, 55}
For a complete series, you need to begin with p equal to 0 and repeat (r - 1) times.
For more efficient “ though not shorter, I’m afraid “ you can eschew settings by list:
to getFibSeries(r)
set p to 0
set c to 1
set fibSeries to {1}
repeat r - 1 times
tell p + c
set p to c
set c to it
set end of fibSeries to it
end tell
end repeat
return fibSeries
end getFibSeries
getFibSeries(10)
--> {1, 1, 2, 3, 5, 8, 13, 21, 34, 55}
Thanks, Nigel. The way you have it is how I used it; I was just trying to shorten it without understanding that settings by list was slower than a simple series of sets.
Love ‘eschew’ by the way - knew what it meant, but don’t recall ever having used it in a sentence myself.
A Prof of English I know used to say “eschew obfuscation”.
At this level, there’s often a trade-off between one aim and another. Nigel’s last version is probably about as efficient as you’ll get in AppleScript ” without introducing some compromise of one sort or another. However, if you considered the general approach fast enough for a given purpose, and could afford to forgo a little speed, then something like the method below would be a bit more compact. Here, it tends to be faster than your version when producing a series of up to 15 values - but then starts to slow down as it accesses a growing list. (Of course, referencing the list should improve that aspect, albeit lengthening the script again ” but it still wouldn’t usurp Nigel’s version in terms of speed.)
to getFibSeries(r)
set l to {0, 1}
tell l to repeat r - 1 times
set end to end + (item -2)
end repeat
l's rest
end getFibSeries
getFibSeries(10) --> {1, 1, 2, 3, 5, 8, 13, 21, 34, 55}
If only a single value was required, as in some of the earlier examples, we could probably still fine-tune the efficiency of the repeat loop method. The following hybrid routine uses exponentiation to the point at which floating point anomalies would kick in ” and then, if necessary, continues with a repeat loop:
to getFib(r)
if r < 61 then return (1.61803398875 ^ (r - 1.672275938193) + 0.5) div 1
set p to 1.54800875592E+12
set c to 2.504730781961E+12
repeat r - 61 times
tell p + c
set p to c
set c to it
end tell
end repeat
c
end getFib
getFib(25) --> 75025
As I had anticipated (the pressure was on) the getFibSeries is tres elegant.
I particularly like ‘set end to end + …’, and ‘I’s rest’.
As you fully intended :D, getFib(r) boggles the mind. I recognize that 1.61803398875 is the Golden Ratio, Phi, and I knew that Fib(n+1) = round(Fib(n)*Phi), but in a cursory review of R. Knott’s Fibonacci Formulae I didn’t find your formulation, and I haven’t pursued others. Where did you find this one?
I thought I was fairly good at algebra, but I can’t see how you derived your formula from the one on the Web page Adam gave (message #4 above.) “ if indeed you did. (I see Adam’s similarly puzzled.) 1.61803398875 is fairly obviously (1 + 5 ^ 0.5) / 2, but how do you get to the rest of it? The direct AppleScript equivalent of the formula on the Web page is 0.4472135955 * (1.61803398875 ^ n + 0.61803398875 ^ n) div 1. Your formula’s not only shorter, but can handle 5 more numbers before the floating point errors become too great.
My apologies for the delayed reply, guys (unavoidable commitments elsewhere, I’m afraid).
Thanks, Nigel ” I do try to come up with moderately groan-free code, every now and then…
Your doubts about that Web page as a source for the formula were well founded. In fact, I’ve only just had a chance to look at the page (along with a few others). My usual approach in these situations is to cobble together some instinctive attempt at a solution (I can always do with the practice) ” and then, if possible, check the approach against any known methods. However, in this case, the only checking I did was to make sure the algorithm worked for the given range: 0 thru 60.
By cheating, of course ;). Rather than come up with a theoretical formula, I derived one from known results ” using a high Fibonacci index/value pair for a more precise reduction factor, to ensure a value that would work effectively throughout the entire range. (In fact, I used a similar approach, rather than the above formula, to derive the value of Phi in the first place ” using two consecutive values [from items 61 & 60 in the Fibonacci series]: 2.504730781961E+12 / 1.54800875592E+12 → 1.61803398875.)
With regard to the algorithm in question, the Phi ^ n part was fairly obvious ” and a couple of experiments revealed that the required reduction factor appeared to be constant. I used the following script to determine its value:
set Phi to 1.61803398875 (* the so-called "golden ratio" *)
set n to 61 (* index number within the Fibonacci series *)
set v to 2.504730781961E+12 (* the value returned from the above index number *)
(ln Phi ^ n / v) / (ln Phi) -- (requires Satimage.osax)
--> 1.672275938193
See my later post below.
