本文共 2073 字，大约阅读时间需要 6 分钟。

递归与迭代的区别及其应用

递归和迭代是计算机编程中的两种常用方法，虽然它们都能解决问题，但适用的场景和特点有着显著差异。

斐波那契数列的递归与迭代

斐波那契数列是计算机科学中的经典问题之一。递归方法通过不断地将问题分解成更小的子问题来实现：

int fib(int i) {
    if (i < 2) {
        return i == 0 ? 0 : 1;
    }
    return fib(i - 1) + fib(i - 2);
}

而迭代方法则通过循环逐步计算：

int a[40];
a[0] = 0;
a[1] = 1;
for (i = 2; i < 40; i++) {
    a[i] = a[i - 1] + a[i - 2];
}

优点：递归方法代码简洁，易于理解，但需要额外的调用和返回分支，可能导致性能开销较大。

八皇后问题的递归解决方案

八皇后是一个经典的递归问题。程序通过递归方式在棋盘上寻找所有可能的皇后摆放位置，确保每行、每列都没有重复。

int chess[8][8], count = 0;
void NotDanger(int row, int j) {
    for (int i = 0; i < 8; i++) {
        if (chess[i][j] == 1) {
            return -1;
        }
    }
    return 1;
}
void EightQueen(int row, int n, int(*chess)[8]) {
    int chess2[8][8];
    memcpy(chess2, chess, sizeof(chess2));
    if (row == 7) {
        printf("第 %d 种\n", count + 1);
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                printf("%d ", chess2[i][j]);
            }
            printf("\n");
        }
        count++;
        printf("\n");
    } else {
        for (int j = 0; j < n; j++) {
            if (NotDanger(row, j)) {
                memcpy(chess2 + row, chess + row, sizeof(chess2));
                chess2[row][j] = 1;
                EightQueen(row + 1, n, chess2);
            }
        }
    }
}
int main() {
    int chess[8][8];
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            chess[i][j] = 0;
        }
    }
    EightQueen(0, 8, chess);
    printf("总共有 %d 种解决方法!\n\n", count);
    return 0;
}

分治法的应用

分治是一种通过将大问题拆解成小问题来解决的方法。经典的应用是二分查找。以下是实现二分搜索的递归函数：

ElemType refind(ElemType *data, int begin, int end, ElemType num) {
    int mid;
    if (begin > end) {
        return -1;
    }
    mid = (begin + end) / 2;
    if (data[mid] == num) {
        return mid;
    } else if (num > data[mid]) {
        return refind(data, mid + 1, end, num);
    } else {
        return refind(data, begin, mid - 1, num);
    }
}

通过递归调用，快速缩小查找范围，直到找到目标元素或确定不存在。

总结

递归和迭代虽然在实现方式上不同，但在解决算法问题时各有优劣。递归的代码逻辑简单，易于理解，但性能相对较差；迭代则更高效，但代码结构可能显得复杂。两者都可以通过优化，实现快速高效的算法解决方案。