js递归求和1,2,3,..., n,..., 3,2,1?

cjwj
  • 628

js递归求和1,2,3,..., n,..., 3,2,1?

回复
阅读 6.8k
5 个回答

答案楼上其实都有了,然而题目要求递归,
递归吧,我的理解呢,就是尽量避免什么转化过程,尽量少动脑吧?
我就主要说说解这种题的思路吧。
递归的思路就是分阶段求解,然后定终点。
核心就是找fn(n)和fn(n-1)的关系,结合边界条件fn(1),写出一个如下的函数:

function fn(n) {
    // 终点
    if (...) return ...;
    // 递归
    return fn(n-1) + ...;
}

以本题来说,

fn(n) = 1 + 2 + 3 + ... + n-1 + n + n-1 + ... + 3 + 2 + 1;
fn(n-1) = 1 + 2 + 3 + ... + n-1 + ... + 3 + 2 + 1;

fn(n) = fn(n-1) + n-1 + n;

终点

fn(1) = 1;

结合便能写出

function fn(n) {
    if (n==1) return 1; // 终点
    return fn(n-1) + n-1 + n; // 递归关系
}

类似的就同理可得咯

定义f(n) = sum(1, 2, 3, ..., n, ..., 3, 2, 1)

解法一

问题转化为f(n) = 2 * g(n) - n,其中g(n) = sum(1, 2, 3, ..., n)。不用高斯求和法强行递归的话,g(n) = g(n - 1) + n(n > 1),g(n) = 1(n = 1)。

function g(n) {
  if(n > 1) return g(n - 1) + n;
  else if(n == 1) return 1;
}

function f(n) {
  return 2 * g(n) + n;
}

解法二

显然,f(n) = f(n - 1) + n + (n - 1)(n > 1),f(n) = 1(n = 1)。

function f(n) {
  if(n > 1) return f(n - 1) + n + n - 1;
  else if(n == 1) return 1;
}
var a = 1;
for (var i = 2; i < n; i++) {
    a = a + i
}
var sum = 2*a + n;
console.log(sum)

1,2,3,..., n,..., 3,2,1转化为求前n项的和与前n-1的和的和。
于是有了:
1 + 2 + 3 + 4 + ... + n + ... + 3 + 2 + 1 = n(n + 1)/2 + (n - 1)(n - 1 + 1)/2
整理得到 n2

所以:

Math.pow(n, 2)

但是题目又要求用递归做。

const cal = (n) => {
  if(n === 1) {
    return 1;
  }
  return 2 * n + cal(n - 1) - 1;
}

console.log(cal(4)) //16

不用数学的思想 单纯用递归的思想
比如传入4
先执行先序递归 index++
先序递归做value = 1+2+3+4
满足条件后 return;
然后执行后续递归 开始index--
后续递归做value += 3+2+1+0;
var cal = function() {

        var index=0;
        var value=0;
        return function show(n) {
                if(n < 0) return;
                value += index;
                if(index === n)return;
                index++; 
                show(n);
                index--;
                value += index;
                return value;
        }
    };
    cal()(4) // 16
    
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏