递归例题+练习

例题2 斐波那契数列

时间限制：1s

内存限制：128M

 题目描述

斐波那契数列是一个有特殊规律的数列，它的前两项都是 1，从第 3 项开始，该项等于前两项数字之和。现在请你输出斐波那契的第 n 项。

【输入格式】

输入共 1 行：
第 1 行，1 个正整数 n。

【输出格式】

输出共 1 行：
第 1 行，输出斐波那契的第 n 项。

#include <iostream>
using namespace std;

int fib(int i)
{
	if(i <= 0) return 0;
	if(i == 1 || i == 2) return 1;
	return fib(i - 2) + fib(i - 1);
}

int main()
{
	int n;
	cin >> n;
	cout << fib(n) << endl;
    return 0;
}

练习：佩尔数列

时间限制：1s 内存限制：128M

 题目描述

佩尔数列是一个自古以来就知道的整数数列，由递推关系定义。它出现在 2 的算术平方根的近似值以及三角平方数的定义中，也出现在一些组合数学的问题中。
佩尔数的数列从 0 和 1 开始，以后每一个佩尔数都是前面的数的两倍加上再前面的数。最初几个佩尔数是：0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378
例：
2 = 2 * 1 + 0
5 = 2 * 2 + 1
12 = 2 * 5 + 2
......

【输入格式】

一个整数 n。

【输出格式】

一个整数，佩尔数列的第 n 项。

#include <iostream>
using namespace std;

int f(int i)
{
	if(i <= 1) return 0;
	if(i == 2) return 1;
	return f(i - 2) + 2 * f(i - 1);
}

int main()
{
	int n;
	cin >> n;
	cout << f(n) << endl;
	return 0;
}