leetcode 算法-各位相加（递归）

说明

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。

示例:

输入: 38
输出: 2 
解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。

首先是使用递归的方式实现：

解题思路：
1：首先要判断递归截止条件
2：递归的每一步需要做什么
3：一点不要忘记return 递归函数

var addDigits = function (num) {
    const numArr = num.toString().split('')
    // 这是递归截止条件
    if (numArr.length === 1) {
        return num
    }
    let total = 0
    // 拆分递归步骤
    numArr.forEach((item) => {
        total += parseInt(item)
    })
    return addDigits(total)
}

执行效率

进阶:
你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？我思考了良久没有头绪，后来参考一个大佬的代码：

var addDigits = function (num) {
    return ((num - 1) % 9) + 1
}

执行效率也是牛逼

文章可以参考：只看代码很难理解，用到了数学的归纳法，可以对比这三个去理解这个算法。
https://leetcode-cn.com/problems/add-digits/solution/java-o1jie-fa-de-ge-ren-li-jie-by-liveforexperienc/
https://leetcode-cn.com/problems/add-digits/solution/o1jie-fa-can-kao-jiao-you-jie-fa-hou-dui-suan-fa-s/
https://leetcode-cn.com/problems/add-digits/solution/python-hua-tu-jiang-ming-bai-o1zuo-fa-de-yuan-li-b/
https://leetcode-cn.com/problems/add-digits/solution/258ge-wei-xiang-jia-ku-xing-seng-by-kuxingseng/