C++U3-第09课-递归函数的应用

学习目标

 斐波那契数列例题

我们需要求出斐波那契第n项的值是多少

【思路分析】
我们用递归的方式去求解，当第一项和第二项返回1，否则返回前两项的和

当前为第一项和第二项返回1

当前不为第一项和第二项返回前两项的和

定义n并把n输入，带入到递归求解

【参考代码】

#include <iostream>
using namespace std;
int f(int n) {
    //当前为第一项和第二项返回1
    if (n <= 2) {
        return 1;
    }
    //当前不为第一项和第二项返回前两项的和
    return f(n - 1) + f(n - 2);
}
int main() {
    //定义n并把n输入，带入到递归求解
    int n;
    cin >> n;
    cout << f(n);
    return 0;
}

[【递归的应用(一)】Pell数列]

【题意分析】
对于数列找出数列中的第k项

【思路分析】
第i项为2倍的i-1项加上i-2项的和，我们使用递归的方式去求出第k项

采用递归，f(n) 的里返回 pell 数列的第 n 项的值

n为1和n为2的时候分别返回1和2

当n不为1和2到时候返回2*f(i-1)+f(i-2)

定义n输入n,接着输入n个k，将k带入递归求出第k项的值

【参考代码】
#include <iostream>
using namespace std;
//采用递归，f(n) 的里返回 pell 数列的第 n 项的值
long long f(int n) {
    //n为1和n为2的时候分别返回1和2
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    //当n不为1和2到时候返回2*f(i-1)+f(i-2)
    return 2 * f(n - 1) + f(n - 2);
}
int main() {
    //定义n输入n,接着输入n个k，将k带入递归求出第k项的值
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        cout << f(k) << '\n';
    }
    return 0;
}

[【递归的应用(一)】辗转相除法最大公约数]

 枚举会超时

 辗转相除法

【题意分析】
我们对于两个数求出他们的最大公约数

【思路分析】
我们对于两个数进行辗转相除，直到b为0，也就是一边是另一边的倍数

当b为0是输出a

如果b不为0，将b，和a%b带入到递归

【参考代码】
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
    //当b为0是输出a
    if (a % b == 0) return b;
    //如果b不为0，将b，和a%b带入到递归
    return gcd(b, a % b);
}
int main() {
    //定义a和b并输入，将a和b带入到函数递归
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b);
    return 0;
}

初赛知识：