Recursion is evil :-)
I'm playing with Google riddle from some code.jam event.
As a result of play I have function [here without any optimization and argument checking]:
public long findMaxF(long d, long b) {
long f = 0;
if (b==1) {
f=d;
} else if (b==d) {
f=(1<<d)-1; // 2^d - 1
} else {
f = findMaxF(d-1,b)+findMaxF(d-1,b-1)+1;
}
return f;
}
I have even less complicated version giving identical results:
public long findMaxF(long d, long b) {
long f = 0;
if (d<b) b=d;
if (b==1) {
f=d;
} else {
f = findMaxF(d-1,b)+findMaxF(d-1,b-1)+1;
}
return f;
}
I know that it is possible to calculate it without recursion... but I don't know how ;-) My only idea for now was to "simulate" some kind of stack ;-) with keeping list of directions how we moved on recursion tree, but I don't like this idea ;-)
d and
b may be really big, not simply thousands but also millions and billions [but if
b is greater then 32 this method will return something bigger then 2^32 so more then 4 billions with something following]
My code works great with small set of data but totally fails with large :-) For now it fails because StackOverflowError :-) but why not if
d is counted in millions ;-)
Even my idea with simulated stack will fails with such big values.......
I feel that it should be possible to not only avoid recursion [this is sure ;-)] but that this should be done in "linear" way, with 1 pass algorithm....
OK, I divide with you my sadness ;-) I feel better now ;-)
[
Update: 09/07/2008]
Yesterday I decided that it cannot be in this way that I cannot do this ;-)
I decide to analyze this function. I thought in this way, first of all, if we will draw 3d chart of this function and as x we will use d, and as y we will use b, this function will have results only in are between y=1 and line described by y=x.
Additionally when y = 1, this function will return value d [so value of x], and on this line y=x [b=d] it will take value 2
b-1. So I'm interested what kind of function describes value of this function with fixed b value....
I printed results for function for d=20 and b from 1 to 20....
I put it into spreadsheet and checked what if I will calculate f(n)-f(n-1).... :-)
I got some results, and those results was symmetrical... It was a clue ;-)
Difference between next values of function was described by binomial coefficient :-)
Binomial coefficient is described by:
n!/(k!(n-k)!)So I needed to calculate factorial.... Thought by sad memories from fighting with recursion for original function I decided to use "linear" algorithm ;-) When I was using
BigInteger it was working, and was able to calculate binomial coefficient for almost anything in finite time.... but this finite time might be counted in decades ;-)
I analyzed formula to calculate coefficient, changed code, this worked but still was slooooowwww.
Finally I found in
Wikipedia article about
binomial coefficient in programming languages. I used it, and it's working :-)
Similar postsbetaHow to create valid file name?How we may use Google Earth Plugin? :-)How to get negative number from size() in LinkedList in Java? ;-)Abuse of Booleans ;-)Which language is fastest? ;-)