如何确定递归代码的Big-O？

我有以下代码，这是这个问题的答案：https://leetcode.com/problems/add-digits/ https://leetcode.com/problems/add-digits/

class Solution {
public:
    int addDigits(int num) {
        if (!num/10)
            return num;

        long d = 1;
        int retVal = 0;

        while(num / d){
            d *= 10;
        }
        for(d; d >= 1; d/=10){
            retVal += num / d;
            num %= d;
        }
        if (retVal > 9)
            retVal = addDigits(retVal);

        return retVal;
    }
};

不过，作为后续行动，我正在尝试确定 BigO 的增长情况。我第一次尝试计算结果是O(n^n)（我假设因为每个深度的增长直接取决于n每次），这真是令人沮丧。我错了吗？我希望我错了。

在这种情况下它是线性的O(n)因为你打电话addDigits方法递归地没有任何循环以及方法体中的一次

更多细节：确定递归函数的复杂性（大 O 表示法） https://stackoverflow.com/questions/13467674/determining-complexity-for-recursive-functions-big-o-notation

Update： 从递归函数被调用一次的角度来看，它是线性的。然而，在这种情况下，这并不完全正确，因为执行次数几乎不依赖于输入参数。