Day 6

函数递归
1。递归两种不同的传法
 long long jiecheng(int *p){
     if(*p==0||*p==1){
     return 1;
     }
    int current = *p;
     (*p)--;//用指针
     return current*jiecheng(p);
 }

long long Fibonacci(int p){
    if(p==1||p==2){return 1;}
    return Fibonacci(p-1)+Fibonacci(p-2);//传值
}
2.可记忆化递归
记忆化递归是动态规划（Dynamic Programming）的一种实现形式（自顶向下的动态规划），是算法面试和竞赛中必须掌握的核心技巧，它能将原本效率低下的递归算法优化到极高的水平。
这样做可以避免大量重复的计算，从而将算法的时间复杂度从指数级（如 O(2n)）降低到线性或线性对数级（如 O(n)或 O(nlogn)）。
我们需要一个数据结构来存储已经计算过的结果。最常用的数据结构是哈希表（Hash Table）或数组（Array）。
实现步骤：
创建 “备忘录”（Memo）：定义一个全局或静态的哈希表 / 数组，用于存储已经计算过的子问题结果。键（Key）是子问题的参数，值（Value）是子问题的解。
检查 “备忘录”：在递归函数的开头，首先检查当前要解决的子问题是否已经存在于 “备忘录” 中。
如果存在，直接返回 “备忘录” 中存储的结果。
如果不存在，才执行正常的递归计算。
存入 “备忘录”：在计算出子问题的结果后，将其存入 “备忘录”，然后再返回该结果。
典型样例：斐波那契数列
#include <iostream>
#include <unordered_map>

// 1. 创建“备忘录”，使用静态变量确保在多次函数调用间共享
// 键是 n，值是 fibonacci(n) 的结果
static std::unordered_map<int, long long> memo;

long long fibonacci_memo(int n) {
    // 基准条件 (Base Case)
    if (n <= 1) {
        return n;
    }

    // 2. 检查“备忘录”
    // 如果备忘录中已经有结果，直接返回，避免重复计算
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }

    // 3. 如果备忘录中没有，则进行递归计算
    long long result = fibonacci_memo(n - 1) + fibonacci_memo(n - 2);

    // 4. 将计算结果存入“备忘录”
    memo[n] = result;

    // 返回结果
    return result;
}

int main() {
    int n = 45;
    // 每次运行前清空备忘录，以防多次调用main函数时数据干扰
    memo.clear(); 
    std::cout << "Fibonacci(" << n << ") = " << fibonacci_memo(n) << std::endl;
    return 0;
}
核心思想：用空间换时间。通过存储中间结果，避免重复计算。
适用场景：当递归函数存在大量重叠子问题时，记忆化递归是首选的优化方法。
实现方式：通常使用一个哈希表或数组作为 “备忘录”，在递归函数中先查备忘录，再决定是否计算。
3.十进制转二进制
#include<iostream>
#include<string>
using namespace std;
string exchange(int a){
    if(a==0)return "";
    char bit=(a%2)+'0';//转换成ASCII;
    string output=exchange(a/2);
return output+bit;
}