故如虹,知恩;故如月,知明
排名
6
文章
6
粉丝
16
评论
8
{{item.articleTitle}}
{{item.blogName}} : {{item.content}}
ICP备案 :渝ICP备18016597号-1
网站信息:2018-2024TNBLOG.NET
技术交流:群号656732739
联系我们:contact@tnblog.net
欢迎加群交流技术

简单递归的分析方法,递归求和,递归算斐波那契数列

3461人阅读 2018/10/8 10:11 总访问:3841684 评论:0 收藏:0 手机
分类: 随笔

一般分析递归需要知道两个要素

1:递归退出条件
2:任意项的递归公式(除开退出条件)

比如递归求和,递归算斐波那契数列这两个很简单的递归算法


斐波那契求第n项的值
f(1)= 1,f(2)= 1  (递归退出条件)

f(n) = f(n-1)+f(n-2);(任意项的递归公式)

可以把n换成具体的数字带进去算

f(3) = f(2)+f(1) = 1+1 =2;

f(4) = f(3)+f(2) = f(1)+f(2)+f(2) = 1+1+1 = 3

/// <summary>
/// 斐波那契求第n项的值
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public static int FBSum(int n)
{
    if (n == 1 || n == 2)
        return 1;
    return FBSum(n - 1) + FBSum(n - 2);
}

根据写的递归算法看看,第5项的推理过程

FBSum(5) =FBSum(4)+FBSum(3) = FBSum(3)+FBSum(2)+FBSum(2)+FBSum(1)

=FBSum(2)++FBSum(1)+FBSum(2)+FBSum(2)+FBSum(1) = 5



递归求1....n的和

sum(1) = 1     (递归退出条件)

sum(2) = 2+sum(1)

sum(3) = 3+sum(2)

根据上面的分析可得任意项的递归公式

sum(n) = n+sum(n-1);(任意项的递归公式)

/// <summary>
/// 递归函数求和
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public static int Sum(int n)
{
    if (n == 1)
        return 1;
    return Sum(n - 1) + n;
}



递归实现Python蓝桥杯的一道纸张尺寸的题目

【问题描述】

在 ISO 国际标准中定义了 A0 纸张的大小为 1189 mm × 841 mm ,将 A0 纸

沿长边对折后为 A1 纸,大小为 841 mm × 594 mm ,在对折的过程中长度直接取

下整(实际裁剪时可能有损耗)。将 A1 纸沿长边对折后为 A2 纸,依此类推。

输入纸张的名称,请输出纸张的大小。

【输入格式】

输入一行包含一个字符串表示纸张的名称,该名称一定是 A0 、 A1 、 A2 、

A3 、 A4 、 A5 、 A6 、 A7 、 A8 、 A9 之一。

【输出格式】

输出两行,每行包含一个整数,依次表示长边和短边的长度。

【样例输入 1 】

A0

【样例输出 1 】

1189

841

【样例输入 2 】

A1

【样例输出 2 】

841

594


这道题题目也比较简单,递归退出条件分析:

A0 = 1189,841

每项的递归规律分析:

A1 = A0.width,A0.height/2

An = A(n-1).widht,A(n-1).hegiht/2

然后就可以写算法了,其实分析出来后算法就很简单了

## 递归实现纸张大小
def paperfunc(n):
    if (n==0):
        return [1189,841]
    return [paperfunc(n-1)[1],paperfunc(n-1)[0]//2]

result = paperfunc(3)
print(result[0])
print(result[1])



实际运用递归解析树什么的:https://www.tnblog.net/aojiancc2/article/details/4785


欢迎加群讨论技术,群:677373950(满了,可以加,但通过不了),2群:656732739

评价