遞歸的介紹

概念:遞歸是指函數直接或間接調用自身的過程。
解釋遞歸的兩個關鍵要素:
基本情況(遞歸終止條件):遞歸函數中的一個條件，當滿足該條件時，遞歸終止，避免無限遞歸。可以理解為直接解決極小規模問題的方法。遞歸表達式(遞歸調用):遞歸函數中的語句，用于解決規模更小的子問題再將子問題的答案合并成為當前問題的答案。

遞歸如何實現

遞歸函數的基本結構如下:
返回類型 函數名(參數列表){基本情況(遞歸終止條件)
if(滿足終止條件){返回終止條件下的結果遞歸表達式(遞歸調用)
}
else if{將問題分解為規模更小的子問題使用遞歸調用解決子問題返回子問題的結果
}

實現過程:

• 將大問題分解為規模更小的子問題。
• 使用遞歸調用解決每個子問題。
• 通過遞歸終止條件來結束遞歸。

設計時需注意的細節:

1. 確保遞歸一定能到遞歸出口，避免無限遞歸，這可能導致TLE(超時)、MLE(超內存)、或RE(運行錯誤)
2. 考慮邊界條件，有時候遞歸出口不止一個。
3. 避免不必要的重復計算，盡可能優化遞歸函數的性能(例如使用記憶化)。

遞歸和循環的比較

遞歸的特點:

1. 直觀、簡潔，易于理解和實現
2. 適用于問題的規模可以通過遞歸調用不斷減小的情況。
3. 可以處理復雜的數據結構和算法，如樹和圖的遍歷。(線段樹)
4. 存在棧溢出風險(棧空間一般只有8MB，所以遞歸層數不宜過深一般不超過1e6層)。

循環的特點:

• 1.直接控制流程，效率較高。(常數小)
• 2.適用于問題的規模沒有明顯的縮減，或者需要特定的迭代次數。(二元組)
• 3.適合處理大部分的動態規劃問題

在部分情況下，遞歸和循環可以相互轉化。(DFS)

例題:

（一、斐波那契數列，帶備忘錄的遞歸）

已知F(1)=F(2)= 1;n>3時F(n)=F(n-1)+F(n-2)
輸入n，求F(n)，n<=100000，結果對1e9+7取模

如果直接使用遞歸，難以算出結果，需要優化

時間復雜度為

#include <bits/stdc++.h>  
using namespace std;
using ll = long long; // 使用別名ll代表long long  const int N = 1e5 + 9;
const ll p = 1e9 + 7; // 定義模數p  ll fib(int n) {if (n <= 2) return 1; // 基準情況  return (fib(n - 1) + fib(n - 2)) % p; // 計算并存儲結果  
}int main() {int n;cin >> n;for (int i = 1; i <= n; ++i) {cout << fib(i) << '\n'; // 輸出每個i的fibonacci數并換行  }return 0;
}

?優化方法：帶備忘錄的遞歸

時間復雜度為

#include <bits/stdc++.h>  
using namespace std;
using ll = long long; // 使用別名ll代表long long  const int N = 1e5 + 9;
const ll p = 1e9 + 7; // 定義模數p  ll dp[N]; // 定義dp數組作為備忘錄  // 帶備忘錄的遞歸
ll fib(int n) {if (dp[n]) return dp[n]; // 如果已經計算過，直接返回結果，不需要重復計算if (n <= 2) return 1; // 基準情況  return dp[n] = (fib(n - 1) + fib(n - 2)) % p; // 計算并存儲結果  
}int main() {int n;cin >> n;for (int i = 1; i <= n; ++i) {cout << fib(i) << '\n'; // 輸出每個i的fibonacci數并換行  }return 0;
}

（二、數的計算）

藍橋 OJ 760

用戶登錄

題目描述
輸入一個自然數 n(n < 1000)，我們對此自然數按照如下方法進行處理:
1.不作任何處理;
2.在它的左邊加上一個自然數,但該自然數不能超過原數的一半;

3.加上數后,繼續按此規則進行處理,直到不能再加自然數為止。問總共可以產生多少個數。
輸入描述
輸入一個正整數 n。
輸出描述
輸出一個整數，表示答案。
輸入輸出樣例

思路：

我們可以將題意轉化一下，轉化成在右邊加上自然數，因為“在左邊加上0”是沒有意義的，不會改變這個數字大小，所以我們在右邊也不能加上0。
用一個數組a記錄下數字每一位上的數字是多少，然后枚舉當前位上的數字，遞歸的向下去求方案數并求和即可。

#include<bits/stdc++.h>
using namespace std;const int N = 20;
int a[N];int dfs(int dep)// dep表示當前的深度
{int res = 1;// 枚舉當前這層可以放下哪些數字for (int i = 1; i <= a[dep - 1] / 2; ++i){a[dep] = i;res += dfs(dep + 1);}return res;
}int main()
{int n; cin >> n;a[1] = n;cout << dfs(2) << '\n';return 0;
}

（三、計算函數值）

用戶登錄

問題描述：

在一個神秘的世界中，有一個傳說中的神秘花園，被認為蘊藏著無限的知識。但要進入這個花園，訪客必須解決一道神秘數學難題，這個難題與一個特殊的數學函數——“神秘函數”S(c)——緊密相關。

神秘函數S(c)的定義：

• 當c為0時，S(0) = 1。
• 當c為偶數時，S(c) = S(c/2)。
• 當c為奇數時，S(c) = S(c-1) + 1。

任務：

編寫一個程序，根據輸入的正整數α，計算神秘函數S(α)的值。正確解答這道難題將獲得通行證，得以進入神秘花園探索知識寶藏。

輸入格式：

輸入包含一個正整數α（1 ≤ α ≤ 10^6），表示要求解的神秘函數問題中的參數。

輸出格式：

輸出一個整數，表示神秘函數S(α)的值，即成功解決問題后得到的答案。

解題思路

這道題主要思想就是遞歸調用，實現了對遞推方程的求解問題。

首先，我們定義一個函數，它所實現的功能是返回通過神秘函數運算得到的值。

那么，我們可以分為三個部分：

1. 當 x=0?時，我們知道通過神秘函數運算得到的值為?1，因此直接返回?1。
2. 當?x?為偶數時，由于 S(x)=S(x/2)，故我們只需要計算 S(x/2)?的值并返回即可，這時我們再次調用我們定義的函數并以 x/2?為初始值。
3. 當?x?為奇數時，由于 S(x)=S(x?1)+1，故我們只需要計算S(x?1)?的值并返回 S(x?1)+1?即可，這時我們再次調用我們定義的函數并以 x?1?為初始值。

經過如上過程便可以得出最終結果。

#include <bits/stdc++.h>// 奇數減一會變成偶數,偶數除以2
// 等價與我們最多使用兩次代價使 x 除以 2
// 除以 2 最多 log 次
// O(log)void solve(const int &Case) { int x;std::cin >> x;std::function<int(int)> S = [&](int x) {if (x == 0)return 1;if (x % 2 == 0) {return S(x / 2);}return S(x - 1) + 1;};std::cout << S(x) << '\n';
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int T = 1;for (int i = 1; i <= T; i++)solve(i);return 0;
}

?今天就先到這了！！！

看到這里了還不給博主扣個：
?? 點贊??收藏 ?? 關注！

你們的點贊就是博主更新最大的動力！
有問題可以評論或者私信呢秒回哦。