[Solved]: Recursive function calculating number of ways to sum $a + 2 b + 3 c = x$

Problem Detail: 

Using python need to code a recursive function with one input and no global integers that calculates the number of options to get $x$ using $a*1+b*2+c*3$.

Say $x=3$, there are four options: $\lbrace (1,1,1),(1,2),(2,1),(3)\rbrace$.

Asked By : yuvalz

Answered By : Yuval Filmus

Recursion is a pretty bad choice here, but here is the recursion you could use: $$ f(n) = \begin{cases} 0, & n < 0, \\ 1, & n = 0, \\ f(n-1) + f(n-2) + f(n-3), & n > 0.\end{cases} $$ For example, $$ \begin{align*} f(-2) &= 0, \\ f(-1) &= 0, \\ f(0) &= 1, \\ f(1) &= f(0) + f(-1) + f(-2) = 1, \\ f(2) &= f(1) + f(0) + f(-1) = 2, \\ f(3) &= f(2) + f(1) + f(0) = 4. \end{align*} $$ The dynamic programming approach implied by this example is a much better idea; it can be implemented in constant space and linear time, whereas the recursion will take linear space and exponential time. You could also use matrix powering to compute $f$: $$ f(n) = \begin{bmatrix} 1 & 0 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \end{bmatrix}^n \begin{bmatrix} 1 \\ 1 \\ 2 \end{bmatrix}. $$ The generating function is $$ \sum_{n=0}^\infty f(n) x^n = \frac{1}{1-x-x^2-x^3}. $$ Finally, you can also find an explicit solution: $$ \begin{align*} f(n) &= \mathrm{round}(Cx^n), \\ C &= \frac{1}{3} + \frac{\sqrt[3]{847+33\sqrt{33}}}{66} + \frac{4}{3\sqrt[3]{847+33\sqrt{33}}}, \\ x &= \frac{1 + \sqrt[3]{19-3\sqrt{33}} + \sqrt[3]{19+3\sqrt{33}}}{3}. \end{align*} $$ This explicit solution isn't very helpful since you need a lot of precision, but it does give you the correct asymptotics; note $C \approx 0.6184199223$ and $x \approx 1.839286756$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7490