Problem 1: Number of k in Recursion (100pts)

Problem

In lab01 Problem 3, we used a loop to define the number_of_k function. In this problem, you are required to implement the same function using recursion instead of a loop.

Write a function that takes two non-negative integers, n and k, and returns the number of occurrences of k in n.

For example, number_of_k(1234321, 2) returns 2, since 1234321 consists of 1, 2, 3, 4, 3, 2, 1, and there are two 2's in it.

在 lab01 Problem 3 中，我们使用循环来定义 number_of_k 函数。在这个问题中，要求你使用递归而不是循环来实现相同的函数。

编写一个函数，它接受两个非负整数 n 和 k，并返回 k 在 n 中出现的次数。

例如，number_of_k(1234321, 2) 返回 2，因为 1234321 由 1, 2, 3, 4, 3, 2, 1 组成，其中有两个 2。

def number_of_k(n, k):
    """Return the number of occurrences of k in each digit of a non-negative
    integer n.

    >>> number_of_k(999, 9)
    3
    >>> number_of_k(1234321, 2)
    2
    >>> # Do not use while/for loops!
    >>> from construct_check import check
    >>> # ban iteration
    >>> check(LAB_SOURCE_FILE, 'number_of_k', ['While', 'For'])
    True
    """
    "*** YOUR CODE HERE ***"

Hints

• 还是可以 str 逃课。

Solutions

注意 number_of_k(0, 0) 应返回 1，所以 base case 应为只剩一位的情况。

def number_of_k(n, k):

    # Base case
    if n < 10:
        if n == k: return 1
        else: return 0

    # Check the last digit of n (n % 10)
    last_digit = n % 10

    # The count from the current last digit is 1 if it equals k, otherwise 0.
    # Then recursively call the function on the remaining digits (n // 10) 
    # and add the result to the current count.
    if last_digit == k: 
        return number_of_k(n // 10, k) + 1
    else:
        return number_of_k(n // 10, k)

或者使用三元运算符

def number_of_k(n, k):

    # Base case
    if n < 10:
        return 1 if n == k else 0

    # Check the last digit of n (n % 10)
    last_digit = n % 10

    # The count from the current last digit is 1 if it equals k, otherwise 0.
    count_of_k = 1 if last_digit == k else 0

    # Recursively call the function on the remaining digits (n // 10) 
    # and add the result to the current count.
    return count_of_k + number_of_k(n // 10, k)

---

str

def number_of_k(n, k):
    return str(n).count(str(k))

---

压行

def number_of_k(n, k):
    return 1 if n == k else 0 if n < 10 else number_of_k(n // 10, k) + (1 if n % 10 == k else 0)