The number of partitions of a positive integer n, using parts up to size m, is the number of ways in which n can be expressed as the sum of positive integer parts up to m in increasing order. For example, the number of partitions of 6 using parts up to 4 is 9.

    1. 6 = 2 + 4
    2. 6 = 1 + 1 + 4
    3. 6 = 3 + 3
    4. 6 = 1 + 2 + 3
    5. 6 = 1 + 1 + 1 + 3
    6. 6 = 2 + 2 + 2
    7. 6 = 1 + 1 + 2 + 2
    8. 6 = 1 + 1 + 1 + 1 + 2
    9. 6 = 1 + 1 + 1 + 1 + 1 + 1

    We will define a function count_partitions(n, m) that returns the number of different partitions of n using parts up to m. This function has a simple solution as a tree-recursive function, based on the following observation:
    The number of ways to partition n using integers up to m equals

    1. the number of ways to partition n-m using integers up to m, and
    2. the number of ways to partition n using integers up to m-1.

    To see why this is true, observe that all the ways of partitioning n can be divided into two groups: those that include at least one m and those that do not. Moreover, each partition in the first group is a partition of n-m, followed by m added at the end. In the example above, the first two partitions contain 4, and the rest do not.
    Therefore, we can recursively reduce the problem of partitioning n using integers up to m into two simpler problems: (1) partition a smaller number n-m, and (2) partition with smaller components up to m-1.
    To complete the implementation, we need to specify the following base cases:

    1. There is one way to partition 0: include no parts.
    2. There are 0 ways to partition a negative n.
    3. There are 0 ways to partition any n greater than 0 using parts of size 0 or less.
      1. >>> def count_partitions(n, m):
      2.      """Count the ways to partition n using parts up to m."""
      3.      if n == 0:
      4.          return 1
      5.      elif n < 0:
      6.          return 0
      7.      elif m == 0:
      8.          return 0
      9.      else:
      10.          return count_partitions(n-m, m) + count_partitions(n, m-1)
      11. >>> count_partitions(6, 4)
      12. 9
      13. >>> count_partitions(5, 5)
      14. 7
      15. >>> count_partitions(10, 10)
      16. 42
      17. >>> count_partitions(15, 15)
      18. 176
      19. >>> count_partitions(20, 20)
      20. 627
      We can think of a tree-recursive function as exploring different possibilities. In this case, we explore the possibility that we use a part of size m and the possibility that we do not. The first and second recursive calls correspond to these possibilities.
      Implementing this function without recursion would be substantially more involved. Interested readers are encouraged to try.