C++递归函数 #

returnType recursion(parameters) {
    if (baseCase) {
        // 基准情况：直接返回结果
        return baseValue;
    }
    // 递归调用
    return recursion(smallerProblem);
}

// n! = n * (n-1)!
// 0! = 1

int factorial(int n) {
    if (n <= 1) {  // 基准情况
        return 1;
    }
    return n * factorial(n - 1);  // 递归调用
}

int main() {
    std::cout << factorial(5) << std::endl;  // 120
    return 0;
}

// F(n) = F(n-1) + F(n-2)
// F(0) = 0, F(1) = 1

int fibonacci(int n) {
    if (n <= 0) return 0;  // 基准情况
    if (n == 1) return 1;  // 基准情况
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    for (int i = 0; i < 10; i++) {
        std::cout << fibonacci(i) << " ";
    }
    // 0 1 1 2 3 5 8 13 21 34
    return 0;
}

// x^n = x * x^(n-1)
// x^0 = 1

double power(double x, int n) {
    if (n == 0) return 1;
    if (n < 0) return 1.0 / power(x, -n);
    return x * power(x, n - 1);
}

// 优化：快速幂
double fastPower(double x, int n) {
    if (n == 0) return 1;
    if (n < 0) return 1.0 / fastPower(x, -n);
    
    double half = fastPower(x, n / 2);
    if (n % 2 == 0) {
        return half * half;
    } else {
        return x * half * half;
    }
}

// 欧几里得算法
// gcd(a, b) = gcd(b, a % b)
// gcd(a, 0) = a

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

int main() {
    std::cout << gcd(48, 18) << std::endl;  // 6
    return 0;
}

int arraySum(int arr[], int size) {
    if (size <= 0) return 0;
    return arr[size - 1] + arraySum(arr, size - 1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    std::cout << arraySum(arr, 5) << std::endl;  // 15
    return 0;
}

int arrayMax(int arr[], int size) {
    if (size == 1) return arr[0];
    int maxOfRest = arrayMax(arr, size - 1);
    return (arr[size - 1] > maxOfRest) ? arr[size - 1] : maxOfRest;
}

int binarySearch(int arr[], int left, int right, int target) {
    if (left > right) return -1;  // 未找到
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) return mid;
    if (arr[mid] > target) {
        return binarySearch(arr, left, mid - 1, target);
    } else {
        return binarySearch(arr, mid + 1, right, target);
    }
}

void reverseArray(int arr[], int left, int right) {
    if (left >= right) return;
    
    std::swap(arr[left], arr[right]);
    reverseArray(arr, left + 1, right - 1);
}

int strLength(const char* str) {
    if (*str == '\0') return 0;
    return 1 + strLength(str + 1);
}

void reverseString(char* str, int left, int right) {
    if (left >= right) return;
    
    std::swap(str[left], str[right]);
    reverseString(str, left + 1, right - 1);
}

bool isPalindrome(const char* str, int left, int right) {
    if (left >= right) return true;
    if (str[left] != str[right]) return false;
    return isPalindrome(str, left + 1, right - 1);
}

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int treeHeight(TreeNode* root) {
    if (root == nullptr) return 0;
    return 1 + std::max(treeHeight(root->left), treeHeight(root->right));
}

int countNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

void preorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    
    std::cout << root->val << " ";  // 访问根
    preorderTraversal(root->left);   // 遍历左子树
    preorderTraversal(root->right);  // 遍历右子树
}

void inorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    
    inorderTraversal(root->left);    // 遍历左子树
    std::cout << root->val << " ";   // 访问根
    inorderTraversal(root->right);   // 遍历右子树
}

// 非尾递归
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // 乘法在递归之后
}

// 尾递归
int factorialTail(int n, int accumulator = 1) {
    if (n <= 1) return accumulator;
    return factorialTail(n - 1, n * accumulator);  // 递归是最后操作
}

#include <unordered_map>

std::unordered_map<int, long long> memo;

long long fibonacciMemo(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }
    
    memo[n] = fibonacciMemo(n - 1) + fibonacciMemo(n - 2);
    return memo[n];
}

// 斐波那契的动态规划实现
long long fibonacciDP(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    
    long long prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        long long curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

// 递归版本
int sumRecursive(int n) {
    if (n <= 0) return 0;
    return n + sumRecursive(n - 1);
}

// 迭代版本
int sumIterative(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

// 危险：深度递归可能导致栈溢出
void deepRecursion(int n) {
    if (n <= 0) return;
    deepRecursion(n - 1);  // n很大时可能栈溢出
}

// 解决：使用迭代或尾递归优化

// 朴素斐波那契有大量重复计算
int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);  // 重复计算
}

// 解决：使用记忆化

// 错误：缺少基准情况
int badRecursion(int n) {
    return badRecursion(n - 1);  // 无限递归
}

// 正确：添加基准情况
int goodRecursion(int n) {
    if (n <= 0) return 0;  // 基准情况
    return n + goodRecursion(n - 1);
}

int recursion(int n) {
    // 首先检查基准情况
    if (n <= 0) return 0;
    
    // 然后进行递归
    return n + recursion(n - 1);
}

// 错误：问题规模没有减小
int bad(int n) {
    return bad(n);  // 无限递归
}

// 正确：问题规模减小
int good(int n) {
    if (n <= 0) return 0;
    return n + good(n - 1);
}

std::unordered_map<int, long long> cache;

long long compute(int n) {
    if (cache.find(n) != cache.end()) {
        return cache[n];
    }
    
    long long result = /* 计算 */;
    cache[n] = result;
    return result;
}