recursion - Algorithm to find the number of ways a number can be written as a sum of two or more positive numbers -

it's homework question , has solved using dyanmic programming approach.

what i've managed far that:

let f(x) denote number of times x can written:

then f(x) = f(x - 1) + 1 ; f(5) = f(4) + 1 (5 = 4 + 1)

but don't think right approach. help?

an example of problem is:

number of ways 4 can written:

4: 3 + 1 4: (2 + 1) + 1 4: 2 + 2 4: (1 + 1) + (1 + 1) 

this representation call partition. solved in different ways.

for example, let's say

f(x, m) - number of partitions of x  such largest number in partition m 

then

f(x, m) = sum of f(x - m, k) (1 <= k <= m), (k<=x-m), because f(x, y) = 0 (y > x) 

for example ( let's count number partition (f(x, x) = 1))

f(1, 1) = 1 f(2, 1) = f(1, 1) = 1 f(2, 2) = 1 f(3, 1) = f(2, 1) = 1 f(3, 2) = f(1, 1) = 1 //+ f(1, 2) 0 f(4, 1) = f(3, 1) = 1  f(4, 2) = f(2, 1) + f(2, 2) = 2 f(4, 3) = f(1, 1) = 1 // + f(1, 2) + f(1, 3) zeroes f(4, 4) = 1 

so sum of f(4, 1), f(4, 2), f(4, 3), f(4, 4) = 5 ( 4 if not count 4 partition)