递归汉明数生成函数输出顺序与预期不符的原因咨询

Let's break down exactly what's happening here—this is a classic case of understanding the execution order of recursive calls.

First, let's recap your original code and the behavior you saw:

Original Code #

def is_hamming_numbers(x):
    if x==1:
        return True
    if x%2==0:
        return is_hamming_numbers(x/2)
    if x%3==0:
        return is_hamming_numbers(x/3)
    if x%5==0:
        return is_hamming_numbers(x/5)
    return False

def hamming_numbers_sequence(x):
    if x==1:
        return 1
    hamming_numbers_sequence(x - 1)  # Recursive call first
    if is_hamming_numbers(x)==True:
        print('%s'%x,end=' ')

hamming_numbers_sequence(10)

Actual Output: 2 3 4 5 6 8 9 10
Your Expected Output: 10 9 8 5 4 3 2 (note: 6 is also a Hamming number, so it would appear in the adjusted output too!)

Why the Order Is Reversed #

Recursion works by first resolving all the "child" calls before finishing the "parent" call. Here's the step-by-step execution flow for your original function:

1. When you call hamming_numbers_sequence(10), the first thing it does is call hamming_numbers_sequence(9).
2. hamming_numbers_sequence(9) immediately calls hamming_numbers_sequence(8), and this chain continues all the way down to hamming_numbers_sequence(1).
3. hamming_numbers_sequence(1) hits the base case and returns 1. Now we start "backtracking" up the recursive chain:
   • Back to x=2: We've finished the recursive call to x=1, so now we check if 2 is a Hamming number (yes) and print it.
   • Back to x=3: Finished the x=2 call, check if 3 is a Hamming number (yes) and print it.
   • This continues up to x=10: After finishing the x=9 call, we check if 10 is a Hamming number (yes) and print it.

Because we're printing after resolving the recursive call for the smaller number, we end up printing values from smallest to largest as we backtrack.

Fixing the Order (Your Adjusted Code) #

When you reorder the statements to print first, then make the recursive call:

def hamming_numbers_sequence(x):
    if x==1:
        return 1
    if is_hamming_numbers(x)==True:
        print('%s'%x,end=' ')  # Print current x first
    hamming_numbers_sequence(x - 1)  # Then recurse on smaller x

Now the execution flow changes:

1. Call hamming_numbers_sequence(10): Check if 10 is a Hamming number (yes) → print 10. Then call hamming_numbers_sequence(9).
2. Call hamming_numbers_sequence(9): Check if 9 is a Hamming number (yes) → print 9. Then call hamming_numbers_sequence(8).
3. This continues down to x=1, which hits the base case and returns.

Since we're printing the current value before moving to the smaller number, we print values from largest to smallest—matching your expected order.

Quick Note on Your Expected Output #

Just a small correction: 6 is also a valid Hamming number (2×3), so your adjusted code would actually output 10 9 8 6 5 4 3 2 instead of the sequence you listed. That's just a minor detail, but it's good to note!

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