1.题目

2.解法

2.1 递归——逻辑运算符的短路

2.1.1 思路

n=0时退出递归。但题目不允许用if等关键字。 利用逻辑运算符的短路特性，我们可以将判断是否为递归的出口看作 A && B 表达式中的 A 部分，递归的主体函数看作 B 部分。如果不是递归出口，则返回 True，并继续执行表达式 B 的部分，否则递归结束。当然，你也可以用逻辑运算符 || 给出类似的实现，这里我们只提供结合逻辑运算符 && 的递归实现。

2.1.2 代码

n<=0时退出

class Solution { public int sumNums(int n) { boolean flag=n>0&&(n+=sumNums(n-1))>0; return n; } }

2.1.3 复杂度

时间复杂度O(N) 空间复杂度O(N)

2.1.4 结果

---

2.2 快速乘

2.2.1 思路

…

俄罗斯农民乘法

2.2.2 代码

class Solution { public int sumNums(int n) { int ans = 0, A = n, B = n + 1; boolean flag; flag = ((B & 1) > 0) && (ans += A) > 0; A <<= 1; B >>= 1; flag = ((B & 1) > 0) && (ans += A) > 0; A <<= 1; B >>= 1; flag = ((B & 1) > 0) && (ans += A) > 0; A <<= 1; B >>= 1; flag = ((B & 1) > 0) && (ans += A) > 0; A <<= 1; B >>= 1; flag = ((B & 1) > 0) && (ans += A) > 0; A <<= 1; B >>= 1; flag = ((B & 1) > 0) && (ans += A) > 0; A <<= 1; B >>= 1; flag = ((B & 1) > 0) && (ans += A) > 0; A <<= 1; B >>= 1; flag = ((B & 1) > 0) && (ans += A) > 0; A <<= 1; B >>= 1; flag = ((B & 1) > 0) && (ans += A) > 0; A <<= 1; B >>= 1; flag = ((B & 1) > 0) && (ans += A) > 0; A <<= 1; B >>= 1; flag = ((B & 1) > 0) && (ans += A) > 0; A <<= 1; B >>= 1; flag = ((B & 1) > 0) && (ans += A) > 0; A <<= 1; B >>= 1; flag = ((B & 1) > 0) && (ans += A) > 0; A <<= 1; B >>= 1; flag = ((B & 1) > 0) && (ans += A) > 0; A <<= 1; B >>= 1; return ans >> 1; } }

2.2.3 复杂度

时间复杂度：O(logn)。快速乘需要的时间复杂度为O(logn)。 空间复杂度：O(1)。只需要常数空间存放若干变量。

2.2.4 结果