计算1+2+3+...+100，使用递归算法实现。

Question

计算1+2+3+...+100，使用递归算法实现。不能使用循环语句？请问这个题目的思路是什么

Answer 1

 #include <stdio.h>
int foo(int acc, int n)
{
    if (n > 100) return acc;
    return foo(acc + n, n + 1);
}
int main()
{
    int i = foo(0, 1);
    printf("%d", i);
}

Answer 2

int F(x){
if(x==1) return 1;
else
return x+F(x-1);
}
F(100)就是答案了。

Answer 3

以下是笔者的一个思路，仅供参考：

package org.byron4j;

public class Recursion4Add {
public static void main(String[] args) {
System.out.println(recursion(100, 1));;
}

/**
 * f(1)=1
 * f(n)=f(n-1)+n
 * 实现思路：不允许循环，则借助index作为计数器，通过index步增来控制累加运算
 * @param startNum
 * @param index
 * @return
 */
private static int recursion(int startNum, int index){

    if( 100 != index )  
        startNum = recursion(startNum + index,++index);
    return startNum;
}

}

Answer 4

int F(x){
if(x==1) return 1;
else
return x+F(x-1);
}

Answer 5

递归算法要注意的有两点：
1） f(n) 和 f(n -1)之间的关系
2） 递归结束条件

以 1+2+3+...+100 为例：
我们要实现一个方法 f(n)来求 1+2+3+...+n，即f(100)就可以得到 1+2+3+...+100

现在，我们分析一下 f(n) 和f(n-1)的关系：
f（n） = 1+2+3+...+n
f（n - 1） = 1+2+3+...+n -1
可知 ：
f（n） = f( n-1 ) + n

然后再确定一下递归结束条件，这里是 n == 0 时结束，所以这个方法可以这样实现（这里我使用lua实现，其实知道原理，用什么语言都一样）
function f( n )
-- 判断输入参数的类型（这里只是提醒对函数入口作校验，根据需求，添加验证，以增加程序的健壮性）
if type(n) ~= number then
print("输入的参数类型有错误")
return 0
end

if n == 0 then
    return 0
end
return n + f(n-1)

end

Answer 6

int F(x){
if(x==1) return 1;
else
return x+F(x-1);
}