面试题:使用递归的方法计算1到100的累加。-阿里云开发者社区

开发者社区> 264971589117404837> 正文

面试题:使用递归的方法计算1到100的累加。

简介: 今天去面试,遇到这道题目,有段时间没写程序了,温习一下: 题目是使用递归的方法计算1到100的累加,也就是计算1+2+3+4+........+100。大家想必已经听说过高斯如何计算这道题的故事,也知道答案是5050。
+关注继续查看
今天去面试,遇到这道题目,有段时间没写程序了,温习一下:

题目是使用递归的方法计算1到100的累加,也就是计算1+2+3+4+........+100。大家想必已经听说过高斯如何计算这道题的故事,也知道答案是5050。我整理了一下使用递归解决的思路,与大家分享。

递归的特点就是递归函数本身会调用自己,对应到逻辑上就是一段逻辑会使用这段逻辑自身。要使用递归的方法解决这道题,就要先用递归的思维方式描叙这道题。

我们来看看如何描叙题目本身,最直观的描叙:“从1开始,后一个数加上前一个数,后一个数是前一个数加一所得,一直加到100”,但这种描叙无法转化为递归的方法。我们试着按递归的思路思考这个问题,“做一件事情的步骤又包含这个事情步骤的自身”:
  1. 最开始一定是“1”+“某个值
  2. 如果按老思路,这个“某个值”是“1”再加"1",也就是“2”
  3. 到这里,已经完成了一段步骤,并且如果这种思路能形成递归,上面的两步的描叙里面应该会包含对自身同样步骤的一段描叙,但我们仔细想想,里面却没有。
  4. 那我们换个角度思考一下,这个“某个值"也可以是‘2’到‘100’累加的和。到这里,我们看到了点希望,因为”累加的和“这个词就是第1、2步在做的事。
  5. 那么‘2’到‘100’累加的和又应该是‘2’加上”‘3’到‘100’累加的和“,这里我们已经看到递归的迹象了。
  6. 再举一例看看,‘3’到‘100’累加的和又应该是‘3’加上”‘4’到‘100’累加的和“
  7. 对于递归,还有最重要的一点就是这种嵌套何时终止,不然就无穷无尽了。我们看看最后一步,也就是‘100‘到’100‘累加的和是多少?这次我们不用,也无法递归调用了,结果应该直接就是100,所以到这一步,递归终止。

对于整个问题,我们可以进一步抽象为用递归法求两个正整数(m,n)累加和的问题,我们还要考虑m<n, m=n, m>n这三种参数传入方式不同的情况。下面是我写的C#代码,以供参考:

using System;
using System.Collections.Generic;
using System.Text;

namespace Accumulation
{
    class Program
        {
        public static int Accum(int m, int n)
        {
           //对于接受的参数,要考虑m >n,m=n,m<n三种情况。
            if (m < n)
            {
                 return (m + Accum(++m, n)); //如果m<n,返回“m”加上“m+1到n累加的和”
            }

            else
           {
                if (m > n)
               {
                    return (m + Accum(--m, n)); //如果m.n,返回“m”加上“m-1到n累加的和”
            }

                else
                {
                    return n; //如果m=n,直接返回n,这是递归的关键。
                }


           }

        }


        static void Main(string[] args)
        {
            Console.WriteLine(
"The Result of Accumulation from 1 to 100 is:" + Accum(1100));
            Console.WriteLine(
"The Result of Accumulation from 1000 to 1 is:" + Accum(10001));
            Console.WriteLine(
"The Result of Accumulation from 80 to 80 is:" + Accum(8080));
        }

    }

}



版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
10095 0
《算法设计与分析》一一2.4 习题
本节书摘来自华章出版社《算法设计与分析》一 书中的第2章,第2.4节,作者:黄宇 著 ,更多章节内容可以访问云栖社区“华章计算机”公众号查看。
2152 0
在Sql Server中使用Guid类型的列及设置Guid类型的默认值
原文:在Sql Server中使用Guid类型的列及设置Guid类型的默认值 1.列的类型为uniqueidentifier 2.列的默认值可以设为newid(),列类型也可以为 varchar 3.
1006 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13893 0
Py之scikit-learn:机器学习Sklearn库的简介、安装、使用方法(ML算法如何选择)、代码实现之详细攻略
Py之scikit-learn:机器学习Sklearn库的简介、安装、使用方法(ML算法如何选择)、代码实现之详细攻略
33 0
412
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载