递归函数result的时间复杂度分析：a的递减方式与复杂度阶判定

First, let’s restate the function we’re working with—it’s a recursive implementation of the Euclidean algorithm for finding the greatest common divisor (GCD) of two integers:

int result(int a, int b) { 
    if( a %b == 0) return b; 
    a = a % b; 
    return result(b,a); 
}

Let’s break down its behavior and time complexity step by step.

How a Decreases During Recursion #

Here’s what happens to the value of a (and the parameters overall) in each recursive call:

• Base case: If a is divisible by b, we return b right away—no more recursion needed.
• Recursive step: First, we update a to be a % b (the remainder when a is divided by b). By definition, this remainder is always strictly smaller than b.
• Then we swap the parameters for the next call: result(b, a) means the old b becomes the new a, and the remainder (our updated a) becomes the new b.

The critical property here is that each recursive step cuts the larger of the two input values by at least half:

• If b ≤ a/2, then a % b < b ≤ a/2—so the new "larger" value (now b) is already less than half the original a.
• If b > a/2, then a % b = a - b, which is less than a/2 (since b > a/2 implies a - b < a - a/2 = a/2).

No matter the scenario, the bigger number gets reduced to at most half its size every iteration.

Time Complexity #

Since the larger input value is halved (or more) with each recursive call, the number of steps needed grows logarithmically with the initial value of a (if b was larger than a initially, the first call just swaps them, so we still count against the larger of the two numbers).

This means the time complexity is O(log a). It’s definitely not O(log log a)—that’s a far slower-growing complexity reserved for algorithms where each step reduces the problem size by a square root (like some integer factorization methods), not a factor of 2. The Euclidean algorithm’s logarithmic growth is why it’s such a fast, efficient way to compute GCDs.

For context: if your initial a is 1,000,000, log₂(a) is roughly 20—so you’d only need about 20 recursive calls at most. That’s incredibly efficient even for very large integers.

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