递归问题

约 42 个字 58 行代码 预计阅读时间 1 分钟

插入排序的递归

//先由n递归到1，再逐层从栈弹出，相当于把第一层for循环用递归表示
template<class T>
void recursion_insert_sort(T a [] , int n){
    if (n > 1){
        recursion_insert_sort(a,n - 1);
    }
    T t = a[n];
    int j = n - 1;
    while(j >= 0 && a[j] > t){
        a[j + 1] = a[j];
        j--;
    }
    a[j + 1] = t;
}

从数组中找最小值的递归

// 可以传递左右区间
template <class T>
int findMinIndex(T arr[], int left, int right) {
    // 基本情况：当只有一个元素时，返回其下标
    if (left == right) {
        return left;
    }
    int min = findMinIndex(arr, left + 1, right);
    // 比较当前元素和剩余部分的最小值，返回较小值的下标
    return (arr[left] < arr[min]) ? left : min;
}

从数组中二分查找元素 递归实现

template<typename T>
int binarySearch(const T arr[], int left, int right, const T& key) {
    if (left <= right) {
        int mid = left + (right - left) / 2;

        // 如果找到了元素，则返回其索引
        if (arr[mid] == key)
            return mid;

        // 如果中间元素大于 key，则在左侧继续查找
        else if (arr[mid] > key)
            return binarySearch(arr, left, mid - 1, key);

        // 如果中间元素小于 key，则在右侧继续查找
        else 
            return binarySearch(arr, mid + 1, right, key);
    }

    // 如果不存在，则返回 -1
    return -1;
}

递归转置数组

// 递归函数，用于转置数组
template<typename T>
void transposeArray(T arr[], int index, int size) {
    if (index >= size / 2)
        return;

    // 交换当前元素和对应位置的元素
    swap(arr[index], arr[size - 1 - index]);

    // 递归调用，处理下一个位置的元素
    transposeArray(arr, index + 1, size);
}

颜色主题调整

red pink purple indigo blue cyan teal green lime orange brown grey black white

评论区~

有用的话请给我个赞和 star =>
快来跟我聊天~