---
title: "简单斐波那契（递归实现）"
created: 2025-11-28
tags:
  - 算法
---

# 简单斐波那契（递归实现）

## 题目 [简单斐波那契](https://acwing.com/problem/content/719/)

![[image-564c65a6.png]]

## 思路分析

![[image-2984cd50.png]]

普通的递归会tle

可以发现很多值在左边已经提前算过 而右边又重新算一遍

所以可以把值保存在记忆化数组里面 再右边又碰到相同参数时

无需再做递归 只要取出答案即可

这是递归+记忆化数组的第一次接触 后面会用这个引入dp问题

## 代码实现

**tle**

```cpp
#include<bits/stdc++.h>

using namespace std;

int N;

int fibonacci(int n) {

    if (n <= 1)

        return n;

    return fibonacci(n - 1) + fibonacci(n - 2);

}

int main() {

    cin >> N;

    for (int i = 0; i < N; ++i) {

        cout << fibonacci(i);

        if (i < N - 1)

            cout << " ";

    }

    return 0;

}
```

**记忆化搜索**

```cpp
#include<bits/stdc++.h>

using namespace std;

int N;

// 记忆化数组

vector<int> memo(50, -1);

int fibonacci(int n) {

    // 基本情况

    if (n <= 1)

        return n;

    // 如果已经计算过这个值，则直接返回结果

    if (memo[n] != -1)

        return memo[n];

    // 否则，递归计算，并保存结果

    memo[n] = fibonacci(n-1) + fibonacci(n-2);

    return memo[n];

}

int main() {

    cin >> N;

    for (int i = 0; i < N; ++i) {

        cout << fibonacci(i);

        if (i < N-1)

            cout << " ";

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/递归与递推模型/递归/枚举子集|枚举子集]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/递归与递推模型/递归/组合数|组合数]]