递归函数

递归函数是指在函数体内调用自身的函数。递归是一种强大的编程技术，它将复杂问题分解为相似但规模更小的子问题来解决。

递归的基本概念

递归的组成要素

#include <iostream>
 
// 基本递归示例：计算阶乘
int factorial(int n) {
    // 1. 基本情况（递归终止条件）
    if (n <= 1) {
        return 1;
    }
    
    // 2. 递归情况（函数调用自身）
    return n * factorial(n - 1);
}
 
// 递归过程的可视化
int factorialWithTrace(int n, int depth = 0) {
    // 打印缩进
    for (int i = 0; i < depth; ++i) {
        std::cout << "  ";
    }
    std::cout << "factorial(" << n << ") 开始" << std::endl;
    
    int result;
    if (n <= 1) {
        result = 1;
        for (int i = 0; i < depth; ++i) {
            std::cout << "  ";
        }
        std::cout << "基本情况: factorial(" << n << ") = " << result << std::endl;
    } else {
        result = n * factorialWithTrace(n - 1, depth + 1);
        for (int i = 0; i < depth; ++i) {
            std::cout << "  ";
        }
        std::cout << "递归情况: factorial(" << n << ") = " << n << " * factorial(" << (n-1) << ") = " << result << std::endl;
    }
    
    return result;
}
 
int main() {
    std::cout << "=== 递归基本概念 ===" << std::endl;
    
    // 简单调用
    std::cout << "5! = " << factorial(5) << std::endl;
    
    std::cout << "\n=== 递归过程追踪 ===" << std::endl;
    int result = factorialWithTrace(4);
    std::cout << "最终结果: " << result << std::endl;
    
    return 0;
}

递归 vs 迭代

#include <iostream>
#include <chrono>
 
// 递归版本的斐波那契数列（效率低）
long long fibonacciRecursive(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
 
// 迭代版本的斐波那契数列（效率高）
long long fibonacciIterative(int n) {
    if (n <= 1) {
        return n;
    }
    
    long long prev2 = 0;
    long long prev1 = 1;
    long long current;
    
    for (int i = 2; i <= n; ++i) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    
    return current;
}
 
// 优化的递归版本（记忆化）
#include <unordered_map>
 
std::unordered_map<int, long long> memo;
 
long long fibonacciMemoized(int n) {
    if (n <= 1) {
        return n;
    }
    
    // 检查是否已经计算过
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }
    
    // 计算并存储结果
    memo[n] = fibonacciMemoized(n - 1) + fibonacciMemoized(n - 2);
    return memo[n];
}
 
// 性能测试
void performanceTest() {
    std::cout << "=== 性能比较 ===" << std::endl;
    
    int n = 40;
    
    // 测试递归版本
    auto start = std::chrono::high_resolution_clock::now();
    long long result1 = fibonacciRecursive(n);
    auto end = std::chrono::high_resolution_clock::now();
    auto duration1 = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    
    std::cout << "递归版本 fib(" << n << ") = " << result1 
              << ", 耗时: " << duration1.count() << "ms" << std::endl;
    
    // 测试迭代版本
    start = std::chrono::high_resolution_clock::now();
    long long result2 = fibonacciIterative(n);
    end = std::chrono::high_resolution_clock::now();
    auto duration2 = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    
    std::cout << "迭代版本 fib(" << n << ") = " << result2 
              << ", 耗时: " << duration2.count() << "ms" << std::endl;
    
    // 测试记忆化版本
    memo.clear();  // 清空缓存
    start = std::chrono::high_resolution_clock::now();
    long long result3 = fibonacciMemoized(n);
    end = std::chrono::high_resolution_clock::now();
    auto duration3 = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    
    std::cout << "记忆化版本 fib(" << n << ") = " << result3 
              << ", 耗时: " << duration3.count() << "ms" << std::endl;
}
 
int main() {
    performanceTest();
    return 0;
}

经典递归算法

数学计算

#include <iostream>
#include <string>
 
// 1. 最大公约数（欧几里得算法）
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}
 
// 2. 幂运算
double power(double base, int exponent) {
    // 基本情况
    if (exponent == 0) {
        return 1.0;
    }
    if (exponent == 1) {
        return base;
    }
    
    // 处理负指数
    if (exponent < 0) {
        return 1.0 / power(base, -exponent);
    }
    
    // 优化：快速幂算法
    if (exponent % 2 == 0) {
        double half = power(base, exponent / 2);
        return half * half;
    } else {
        return base * power(base, exponent - 1);
    }
}
 
// 3. 数字反转
int reverseNumber(int num, int reversed = 0) {
    if (num == 0) {
        return reversed;
    }
    return reverseNumber(num / 10, reversed * 10 + num % 10);
}
 
// 4. 数字各位数之和
int digitSum(int num) {
    if (num == 0) {
        return 0;
    }
    return (num % 10) + digitSum(num / 10);
}
 
// 5. 判断回文数
bool isPalindrome(const std::string& str, int start = 0, int end = -1) {
    if (end == -1) {
        end = str.length() - 1;
    }
    
    if (start >= end) {
        return true;
    }
    
    if (str[start] != str[end]) {
        return false;
    }
    
    return isPalindrome(str, start + 1, end - 1);
}
 
int main() {
    std::cout << "=== 数学递归算法 ===" << std::endl;
    
    // 最大公约数
    std::cout << "gcd(48, 18) = " << gcd(48, 18) << std::endl;
    std::cout << "gcd(100, 25) = " << gcd(100, 25) << std::endl;
    
    // 幂运算
    std::cout << "power(2, 10) = " << power(2, 10) << std::endl;
    std::cout << "power(3, -2) = " << power(3, -2) << std::endl;
    
    // 数字反转
    std::cout << "reverse(12345) = " << reverseNumber(12345) << std::endl;
    std::cout << "reverse(9876) = " << reverseNumber(9876) << std::endl;
    
    // 数字各位数之和
    std::cout << "digitSum(12345) = " << digitSum(12345) << std::endl;
    std::cout << "digitSum(999) = " << digitSum(999) << std::endl;
    
    // 回文判断
    std::cout << "isPalindrome('racecar') = " << isPalindrome("racecar") << std::endl;
    std::cout << "isPalindrome('hello') = " << isPalindrome("hello") << std::endl;
    
    return 0;
}

数据结构操作

#include <iostream>
#include <vector>
#include <algorithm>
 
// 1. 二分查找
int binarySearch(const std::vector<int>& arr, int target, int left, int right) {
    if (left > right) {
        return -1;  // 未找到
    }
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] > target) {
        return binarySearch(arr, target, left, mid - 1);
    } else {
        return binarySearch(arr, target, mid + 1, right);
    }
}
 
// 2. 快速排序
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}
 
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; ++j) {
        if (arr[j] <= pivot) {
            ++i;
            std::swap(arr[i], arr[j]);
        }
    }
    
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}
 
// 3. 归并排序
void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}
 
void merge(std::vector<int>& arr, int left, int mid, int right) {
    std::vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    
    for (int i = 0; i < k; ++i) {
        arr[left + i] = temp[i];
    }
}
 
// 4. 数组求和
int arraySum(const std::vector<int>& arr, int index = 0) {
    if (index >= arr.size()) {
        return 0;
    }
    return arr[index] + arraySum(arr, index + 1);
}
 
// 5. 数组最大值
int arrayMax(const std::vector<int>& arr, int index = 0) {
    if (index == arr.size() - 1) {
        return arr[index];
    }
    
    int maxOfRest = arrayMax(arr, index + 1);
    return std::max(arr[index], maxOfRest);
}
 
void printArray(const std::vector<int>& arr) {
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}
 
int main() {
    std::cout << "=== 数据结构递归操作 ===" << std::endl;
    
    std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    
    // 数组求和
    std::cout << "数组: ";
    printArray(arr);
    std::cout << "数组和: " << arraySum(arr) << std::endl;
    std::cout << "数组最大值: " << arrayMax(arr) << std::endl;
    
    // 二分查找（需要排序后的数组）
    std::vector<int> sortedArr = {11, 12, 22, 25, 34, 64, 90};
    std::cout << "\n排序后数组: ";
    printArray(sortedArr);
    
    int target = 25;
    int index = binarySearch(sortedArr, target, 0, sortedArr.size() - 1);
    if (index != -1) {
        std::cout << "找到 " << target << " 在索引 " << index << std::endl;
    } else {
        std::cout << "未找到 " << target << std::endl;
    }
    
    // 快速排序
    std::vector<int> quickArr = arr;
    std::cout << "\n快速排序前: ";
    printArray(quickArr);
    quickSort(quickArr, 0, quickArr.size() - 1);
    std::cout << "快速排序后: ";
    printArray(quickArr);
    
    // 归并排序
    std::vector<int> mergeArr = arr;
    std::cout << "\n归并排序前: ";
    printArray(mergeArr);
    mergeSort(mergeArr, 0, mergeArr.size() - 1);
    std::cout << "归并排序后: ";
    printArray(mergeArr);
    
    return 0;
}