今天去面试遇到这道题目有段时间没写了温习下:
题目是使用递归思路方法计算1到100累加也就是计算1+2+3+4+........+100大家想必已经听说过高斯如何计算这道题故事也知道答案是5050我整理了下使用递归解决思路和大家分享
递归特点就是递归本身会自己对应到逻辑上就是段逻辑会使用这段逻辑自身要使用递归思路方法解决这道题就要先用递归思维方式描叙这道题
我们来看看如何描叙题目本身最直观描叙:“从1开始后个数加上前个数后个数是前个数加所得直加到100”但这种描叙无法转化为递归思路方法我们试着按递归思路研究这个问题“做件事情步骤又包含这个事情步骤自身”:
- 最开始定是“1”+“某个值”
- 如果按老思路这个“某个值”是“1”再加"1",也就是“2”
- 到这里已经完成了段步骤并且如果这种思路能形成递归上面两步描叙里面应该会包含对自身同样步骤段描叙但我们仔细想想里面却没有
- 那我们换个角度研究下这个“某个值"也可以是‘2’到‘100’累加和到这里我们看到了点希望”累加和“这个词就是第1、2步在做事
- 那么‘2’到‘100’累加和又应该是‘2’加上”‘3’到‘100’累加和“这里我们已经看到递归迹象了
- 再举例看看‘3’到‘100’累加和又应该是‘3’加上”‘4’到‘100’累加和“
- 对于递归还有最重要点就是这种嵌套何时终止不然就无穷无尽了我们看看最后步也就是‘100‘到’100‘累加和是多少?这次我们不用也无法递归了结果应该直接就是100所以到这步递归终止
对于整个问题我们可以进步抽象为用递归法求两个正整数(m,n)累加和问题我们还要考虑m<n, m=n, m>n这 3种参数传入方式区别情况下面是我写C#代码以供参考:
using ;
using .Collections.Generic;
using .Text;
Accumulation
{
Program
{
public Accum( m, n)
{
//对于接受参数要考虑m >nm=nm<n 3种情况
(m < n)
{
(m + Accum(m, n)); //如果m<n,返回“m”加上“m+1到n累加和”
}
{
(m > n)
{
(m + Accum(--m, n)); //如果m.n,返回“m”加上“m-1到n累加和”
}
{
n; //如果m=n直接返回n这是递归关键
}
}
}
void Main( args)
{
Console.WriteLine("The Result of Accumulation from 1 to 100 is:" + Accum(1, 100));
Console.WriteLine("The Result of Accumulation from 1000 to 1 is:" + Accum(1000, 1));
Console.WriteLine("The Result of Accumulation from 80 to 80 is:" + Accum(80, 80));
}
}
}
2009-1-4 at 9:48