求greatest_divisor()函数的递归实现方案（非最大公约数）

First, let's align on what we're solving here: we need the largest divisor of a single number n that's smaller than n itself (so for prime numbers, this will always be 1). Your iterative version works flawlessly, so let's translate that logic into a recursive approach.

Recursive functions rely on two core pieces: a base case to stop the recursion, and a recursive step that breaks the problem into smaller subproblems. Here's how we can apply that to your task:

Approach #

• Base Case: When our current divisor check reaches 1, we know every integer is divisible by 1, so we return 1 to terminate the recursion.
• Recursive Step: Start checking from n-1 (just like your iterative loop). If the current divisor d divides n evenly, return d right away—since we're checking from largest to smallest, this is our answer. If not, recursively check the next smaller divisor (d-1).

Solution Code #

Here are two clean, functional recursive implementations:

Option 1: Using an Inner Helper Function

This keeps the main function interface clean (no extra parameters needed when calling):

def greatest_divisor(n):
    def recursive_check(d):
        # Base case: 1 divides every number
        if d == 1:
            return 1
        # If d divides n, it's our greatest divisor
        if n % d == 0:
            return d
        # Recurse with the next smaller divisor
        return recursive_check(d - 1)
    
    # Start checking from n-1
    return recursive_check(n - 1)

Option 2: Using a Default Parameter

This avoids the inner function by initializing the divisor on the first call:

def greatest_divisor(n, d=None):
    # Initialize d to n-1 when the function is first called
    if d is None:
        d = n - 1
    # Base case
    if d == 1:
        return 1
    # Check if current d is a valid divisor
    if n % d == 0:
        return d
    # Recurse with the next smaller divisor
    return greatest_divisor(n, d - 1)

Testing the Function #

Both versions behave exactly like your iterative code:

• greatest_divisor(12) returns 6
• greatest_divisor(15) returns 5
• greatest_divisor(17) returns 1

How It Works #

Just like your loop, we start at the largest possible candidate divisor (n-1) and work our way down. The recursion stops either when we find a divisor (returning it immediately) or when we hit 1 (the universal divisor). This mirrors your iterative logic perfectly—we're just replacing the loop with recursive calls instead.

内容的提问来源于stack exchange，提问作者baymurat