递归算法

求 n 的阶乘

题目描述

输入一个正整数 $n$ ，用递归求解 $n$ 的阶乘。

$n$ 的阶乘记作 $n!$，并且 $n!=n\times (n-1)\times (n-2)\times ...\times 3\times 2\times 1$

输入描述

输入为一个正整数 $n$，$(0\le n\le 10)$

输出描述

输出为一个正整数，表示 $n$ 的阶乘

输入输出样例

输入数据

5

输出数据

120

参考代码

P1301001_solution.cpp

#include <iostream>
using namespace std;

long long fact(int x) {
  if (x == 0) return 1; // 递归的终止条件
  return x * fact(x - 1);
}

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

P1301001_solution.py

n = int(input())

def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n-1)
    
print(fact(n))

求斐波那契数列第 $n$ 项

题目描述

输入一个正整数 $n$ ，用递归求解斐波那契数列第 $n$ 项。

输入描述

输入一个正整数 $n$ （$1\le n\le 20$）

输出描述

输出为一个正整数，代表斐波那契数列第 $n$ 项的值。

输入输出样例

输入数据 1

0

输出数据 1

0

输入数据 2

7

输出数据 2

13

参考代码

P1301002_solution.cpp

#include <iostream>
using namespace std;

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

int main() {
  int n;
  cin >> n;

  cout << fib(n) <<endl;  
  return 0;
}

P1301002_solution.py

n = int(input())

def fib(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib(n-1) + fib(n-2)

print(fib(n))

数列前n项求和01

题目描述

有一数列如下： $1,2,4,7,11,16,22\dots \dots$ ，试用递归求该数列前 $n$ 项之和。

输入描述

一个整数 $n$ （ $0<n<10000$ ）

输出描述

包含一行，为一个整数，表示数列求和的结果

输入输出样例

输入数据

6

输出数据

41

参考代码

P1301003_solution.cpp

#include <iostream>
#include <iomanip>
using namespace std;
//计算第n项
int series_sum(int n){
	if ( n==1 ) {
		return 1;
	}else {
		return (n-1) + series_sum(n-1);
	}
}

int main() {
	int n,rlt=0;
	cin>>n;
	
	for (int i = 1; i<=n; i++) {
		rlt = rlt + series_sum(i);
	}
	
	cout<<rlt<<endl;
}

P1301003_solution.py

数列前n项求和02

题目描述

递归求 1/1+1/2+2/3+3/5+5/8+8/13+13/21+21/34 … 的前 $n$ 项的和。

输入描述

输入一个整数 $n$ （$1\le n\le 30$）

输出描述

输出一个小数，即前 $n$ 项之和（保留 3 位小数）。

输入输出样例

输入数据 1

20

输出数据 1

12.660

参考代码

P1301004_solution.cpp

#include <bits/stdc++.h>
using namespace std;

// 求 fibonacci 第 n 项的递归函数
int fib(int n) {
  if (n == 1 || n == 2) return n;
  else return fib(n-1) + fib(n-2);
}

// 数列求和的递归函数
double series_sum(int n) {
    if (n == 1) {
        return 1.0;
    }
    return fib(n-1)/double(fib(n)) + series_sum(n-1);
}

int main() {
  int n;
  cin >> n;

  printf("%.3lf", series_sum(n));
  
  return 0;
}

P1301004_solution.py

求解 N 次方

题目描述

给定一个数 $n$，求它的 $m$ 次方

输入描述

输入为一行，包含两个整数 $n$ 和 $m$，$n$ 与 $m$ 均为整数

输出描述

输入出为一行，表示 $n$ 的 $m$ 次方，结果保留小数点后 4 位

输入输出样例

输入数据 1：

2 5

输出数据 1:

32.0000

输入数据 2:

2 -5

输出数据 2:

0.0313

参考代码

P1301005_solution.cpp

#include <iostream>
using namespace std;

// 这里只考虑整数次方
float pow(float n, int m) {
  if (m == 0) {
    return 1;
  } else if (m < 0) {
    return 1.0 / pow(n, abs(m));
  } else {
    return n * pow(n, m - 1);
  }
}

int main() {
  int n, m;
  cin >> n >> m;
  
  printf("%.4f", pow(n, m));
  
  return 0;
}

P1301005_solution.py

递归求解最大公约数

题目描述

给定两个正整数 $n$ 和 $m$，求它们的最大公约数。

输入描述

输入一行，包含两个正整数 $n$ 和 $m$，以空格分隔，（$n,m\le 100000$）

输出描述

输出一个正整数，即这两个正整数的最大公约数。

输入输出样例

输入数据1

6 9

输出数据2

3

参考代码

P1301006_solution.cpp

#include <iostream>
using namespace std;

int gcd(int a, int b) {
  if(!b) {
      return a;
  }
  return gcd(b, a % b);
}

int main() {
    int a, b;
    cin >> a >> b;
    
    cout << gcd(a, b) << endl;
    
    return 0;
}

P1301006_solution.py