一、Problem

求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

输入: n = 3
输出: 6

二、Solution

方法一：递归

先看看不合法版本的递归写法

class Solution {int f(int n) {if (n == 1)return 1;return n + f(n-1);}public int sumNums(int n) {return f(n);}
}

这里用到了 if，所以不合法，但我们发现 if 判断其实可以省去，只要 n > 0。我们就可以继续递归…

class Solution {int f(int n) {return n > 0 ? n + f(n-1) : 0;}public int sumNums(int n) {return f(n);}
}

复杂度分析

• 时间复杂度：$O(n)$，
• 空间复杂度：$O(n)$，