[2021 spring] CS61A 1.7 recursive functions

http://composingprograms.com/pages/17-recursive-functions.html#example-partitions
课本用例：Partitions
正整数n用不超过m的数字的和表示，方法有count(n, m)种。
通过观察可以发现，count(n, m)可以分为包括m和不包括m的两种情况：

包括m时,种数有count(n - m, m)
不包括m时，种数有count(n,m-1)
即：count(n, m) = count(n - m, m) + count(n, m - 1)

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.

6 = 2 + 4
6 = 1 + 1 + 4
6 = 3 + 3
6 = 1 + 2 + 3
6 = 1 + 1 + 1 + 3
6 = 2 + 2 + 2
6 = 1 + 1 + 2 + 2
6 = 1 + 1 + 1 + 1 + 2
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

the number of ways to partition n-m using integers up to m, and
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:

There is one way to partition 0: include no parts.
There are 0 ways to partition a negative n.
There are 0 ways to partition any n greater than 0 using parts of size 0 or less.

def count_partitions(n, m):
    """Count the ways to partition n using parts up to m."""
    if n == 0:
        return 1
    elif n < 0:
        return 0
    elif m == 0:
        return 0
    else:
        return count_partitions(n-m, m) + count_partitions(n, m-1)

[2021 spring] CS61A 1.7 recursive functions - Partitions

推荐阅读