For foo(x), we need foo(x-i). i is positive, hence for any x we'd need to find the values of foo(<less than x>) to obtain foo(x).
It's best to go with a bottom-up approach, and start with foo(0).
- foo(0) = 1
- foo(1) = foo(0) = 1
- foo(2) = Add all previous values = 2.
- foo(3) = Add all previous values = 4
- foo(4) = Add all previous values = 8
- foo(5) = Add all previous values = 16
- foo(6) = Add all previous values = 32
- foo(7) = Add all previous values = 64
- foo(8) = Add all previous values = 128
- foo(9) = Add all previous values = 256
- foo(10) = Add all previous values = 512