非循环内递归调用n次且仅含if/else的方法时间复杂度是O(N)还是O(1)？

嘿，这个问题问得很到位，咱们直接抓核心点来聊：

首先得明确时间复杂度的本质——它衡量的是算法执行的总操作数和输入规模n之间的增长关系。

回到你的问题：递归方法被调用n次，且调用不在循环里，内部只有if/else（都是常数时间操作）。那咱们拆解来看：

• 每次递归调用里的操作（判断分支、递归调用本身）都是O(1)的，因为没有循环或者其他耗时操作；
• 而总共有n次这样的调用，那总操作数就是 n * O(1)，也就是线性增长的关系。

举个简单的例子就懂了：

public void recursiveFunc(int n) {
    if (n <= 0) {
        return;
    }
    // 这里是O(1)的操作，比如打印或者简单计算
    System.out.println(n);
    recursiveFunc(n - 1);
}

当你传入n=5时，这个函数会被调用6次（5→4→3→2→1→0），每次调用的工作量都是固定的，总工作量和n成正比，所以时间复杂度是O(n)。

那什么时候才是O(1)呢？只有当递归调用的次数和输入n无关，是固定次数的时候。比如一个递归函数不管n多大，最多只调用自己1次，那总操作数是固定的，才会是O(1)。

所以结论很明确：你描述的这种情况，时间复杂度是O(n)，不是O(1)。

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