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

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

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