薛老师讲解C语言函数调用以及递归调用：

以下是C语言中函数调用和递归的详细且全面的知识点总结：

函数调用

函数定义：
在C语言中，函数是一种将一段代码封装起来，以便在需要时重复使用的机制。
函数定义包括返回类型、函数名、参数列表（如果有的话）和函数体。
函数声明：
在调用函数之前，通常需要声明它，以便编译器知道函数的返回类型、名称和参数类型。
函数声明通常放在文件的开头或头文件中。
函数参数：
函数可以接受参数，这些参数在函数被调用时传递给它。
参数可以是值传递（传递参数的副本）或指针传递（传递参数的地址）。
函数调用：
通过指定函数名和必要的参数来调用函数。
函数调用会导致程序跳转到函数体执行，并在函数返回时跳回到调用点。
返回值：
函数可以返回一个值给调用者。
返回值的类型必须与函数定义中指定的返回类型匹配。
如果函数没有返回值（即返回类型为void），则不能使用return语句返回值。
作用域和生命周期：
函数内部定义的变量具有局部作用域，并在函数返回时销毁。
全局变量和静态变量具有更长的生命周期和更广泛的作用域。

递归调用：

函数调用自身称为递归调用。
递归函数通常有一个基本情况（终止条件），以防止无限递归。
递归
递归的基本概念：
递归是一种在函数定义中直接或间接调用该函数自身的编程技术。
递归函数必须有一个基本情况来终止递归。
递归的例子：
计算阶乘、斐波那契数列、树的遍历等都是递归应用的典型例子。
递归的栈和内存管理：
每次递归调用都会在调用栈上分配一个新的栈帧。
如果递归深度太深，可能会导致栈溢出错误。
递归的效率：
递归通常比迭代更慢且更占用内存，因为每次递归调用都会涉及栈帧的创建和销毁。
在某些情况下，可以通过尾递归优化来减少栈的使用。
递归转迭代：
某些递归问题可以通过使用迭代（循环）和显式栈（如数组或链表）来更有效地解决。
递归的调试：
调试递归函数可能比调试非递归函数更具挑战性，因为递归调用涉及多个层次的函数调用。
使用调试器或打印语句来跟踪递归调用的进展和变量的值是有帮助的。
递归的局限性：
并非所有问题都适合用递归解决。例如，对于简单的循环结构，迭代通常更合适。
递归函数的设计需要仔细考虑基本情况，以避免无限递归和栈溢出。
注意事项
在编写递归函数时，确保有一个明确的基本情况来终止递归。
小心处理递归的深度，以避免栈溢出错误。
考虑递归函数的时间复杂度和空间复杂度，以确保它们在合理的时间内和内存使用下运行。
在必要时，可以将递归函数转换为迭代函数以提高效率。
通过理解这些概念，你可以更有效地使用函数调用和递归来解决C语言编程中的问题。

1-100累加和

#include <stdio.h>

int main() {
    int i, sum = 0;
    for (i = 1; i <= 100; i++) {
        sum += i;
    }
    printf("1到100的累加和为：%d\n", sum);
    return 0;
}

1-100累和(加递归方式)

#include <stdio.h>

int sum(int n) {
    if (n == 1) {
        return 1;
    } else {
        return n + sum(n - 1);
    }
}

int main() {
    printf("1到100的累加和为：%d\n",sum);
    return 0;
}

题目1
题目描述：
编写一个递归函数，计算一个整数的阶乘（n!）。

答案：

#include <stdio.h>

unsigned long long factorial(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

int main() {
    int n = 5;
    printf("Factorial of %d is %llu\n", n, factorial(n));
    return 0;
}

题目2
题目描述：
编写一个递归函数，计算斐波那契数列的第n项。

答案：

#include <stdio.h>

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

int main() {
    int n = 10;
    printf("Fibonacci number at position %d is %d\n", n, fibonacci(n));
    return 0;
}

题目3
题目描述：
编写一个递归函数，计算一个数组元素的和。

答案：

#include <stdio.h>

int sumArray(int arr[], int n) {
    if (n == 0) {
        return 0;
    } else {
        return arr[n - 1] + sumArray(arr, n - 1);
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Sum of array elements is %d\n", sumArray(arr, n));
    return 0;
}

题目4
题目描述：
编写一个递归函数，检查一个字符串是否是回文。

答案：

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool isPalindrome(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);
}

int main() {
    char str[] = "radar";
    int n = strlen(str);
    if (isPalindrome(str, 0, n - 1)) {
        printf("%s is a palindrome.\n", str);
    } else {
        printf("%s is not a palindrome.\n", str);
    }
    return 0;
}

题目5
题目描述：
编写一个递归函数，计算一个数的幂（例如，x^n）。

答案：

#include <stdio.h>

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

int main() {
    double x = 2.0;
    int n = 3;
    printf("%.2f raised to the power of %d is %.2f\n", x, n, power(x, n));
    return 0;
}

题目6
题目描述：
编写一个递归函数，计算一个数的汉明重量（即二进制表示中1的个数）。

答案：

#include <stdio.h>

int hammingWeight(int n) {
    if (n == 0) {
        return 0;
    } else {
        return (n & 1) + hammingWeight(n >> 1);
    }
}

int main() {
    int n = 29; // Binary: 11101
    printf("Hamming weight of %d is %d\n", n, hammingWeight(n));
    return 0;
}

题目7
题目描述：
编写一个递归函数，反转一个字符串。

答案：

#include <stdio.h>
#include <string.h>

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

int main() {
    char str[] = "hello";
    reverseString(str, 0, strlen(str) - 1);
    printf("Reversed string is %s\n", str);
    return 0;
}

题目8
题目描述：
编写一个递归函数，计算一个数的最大公约数（GCD）。

答案：

#include <stdio.h>

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

int main() {
    int a = 56, b = 98;
    printf("GCD of %d and %d is %d\n", a, b, gcd(a, b));
    return 0;
}

题目9
题目描述：
编写一个递归函数，生成一个整数数组的所有排列。

答案：

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void permute(int arr[], int left, int right) {
    if (left == right) {
        for (int i = 0; i <= right; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
    } else {
        for (int i = left; i <= right; i++) {
            swap(&arr[left], &arr[i]);
            permute(arr, left + 1, right);
            swap(&arr[left], &arr[i]); // backtrack
        }
    }
}

int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    permute(arr, 0, n - 1);
    return 0;
}

题目10
题目描述：
编写一个递归函数，计算一个数的所有子集。

答案：

#include <stdio.h>

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void generateSubsets(int arr[], int index, int currentSize, int* result, int* resultIndex) {
    if (index == sizeof(arr) / sizeof(arr[0])) {
        printArray(result, currentSize);
        return;
    }

    // Include arr[index] in the result
    result[(*resultIndex)++] = arr[index];
    generateSubsets(arr, index + 1, currentSize + 1, result, resultIndex);

    // Exclude arr[index] from the result
    (*resultIndex)--;
    generateSubsets(arr, index + 1, currentSize, result, resultIndex);
}

int main() {
    int arr[] = {1, 2, 3};
    int result[10];
    int resultIndex = 0;
    generateSubsets(arr, 0, 0, result, &resultIndex);
    return 0;
}

题目11：

编写一个C语言程序，使用递归函数计算一个整数的阶乘（即n! = n (n-1) … * 1）。要求输入一个非负整数n，输出其阶乘的值。

答案：

#include <stdio.h>

// 递归函数计算阶乘
unsigned long long factorial(int n) {
    // 基本情况：0! = 1, 1! = 1
    if (n <= 1) {
        return 1;
    }
    // 递归情况：n! = n * (n-1)!
    return n * factorial(n - 1);
}

int main() {
    int n;

    // 输入非负整数
    printf("请输入一个非负整数: ");
    scanf("%d", &n);

    // 检查输入是否为非负整数
    if (n < 0) {
        printf("错误：输入必须是非负整数。\n");
        return 1;
    }

    // 计算并输出阶乘结果
    unsigned long long result = factorial(n);
    printf("%d 的阶乘是 %llu\n", n, result);

    return 0;
}

题目12：

编写一个C语言程序，使用递归函数实现一个简单的整数数组求和。要求输入一个整数数组和数组的大小，输出数组中所有元素的和。

答案：

#include <stdio.h>

// 递归函数计算数组和，传递数组、数组大小和当前索引
int arraySumRecursive(int arr[], int size, int currentIndex) {
    // 基本情况：当索引超出数组范围时，返回0
    if (currentIndex >= size) {
        return 0;
    }
    // 递归情况：当前元素加上剩余元素的和
    return arr[currentIndex] + arraySumRecursive(arr, size, currentIndex + 1);
}

// 辅助函数，用于简化主函数中的调用
int arraySum(int arr[], int size) {
    return arraySumRecursive(arr, size, 0);
}

int main() {
    int n;

    // 输入数组大小
    printf("请输入数组的大小: ");
    scanf("%d", &n);

    int arr[n];

    // 输入数组元素
    printf("请输入数组的元素: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // 直接调用辅助函数计算数组和
    int sum = arraySum(arr, n);
    printf("数组的和是 %d\n", sum);

    return 0;
}

题目13：

编写一个C语言程序，使用递归函数来检查一个字符串是否是回文（即正读和反读都相同的字符串）。要求输入一个字符串，输出该字符串是否是回文。

答案：

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

// 递归函数检查字符串是否是回文
bool isPalindrome(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);
}

int main() {
    char str[100];

    // 输入字符串
    printf("请输入一个字符串: ");
    scanf("%s", str);

    // 调用递归函数检查字符串是否是回文
    bool result = isPalindrome(str, 0, strlen(str) - 1);

    // 输出结果
    if (result) {
        printf("字符串是回文。\n");
    } else {
        printf("字符串不是回文。\n");
    }

    return 0;
}

递归函数来打印1到100之间的所有奇数

#include <stdio.h>

// 递归函数打印从start到end（不包含end）之间的所有奇数
void printOddNumbers(int start, int end) {
    // 基本情况：如果start大于或等于end，则停止递归
    if (start >= end) {
        return;
    }
    // 检查start是否为奇数，并打印它
    if (start % 2 != 0) {
        printf("%d ", start);
    }
    // 递归调用，从start+1开始，但目标end不变
    // 注意：由于我们每次只增加1，所以需要在下一次调用时检查start+1是否为奇数
    // 但为了优化，我们可以直接传递start+2给递归函数，因为如果start是偶数，
    // 我们就不需要打印它，并且我们知道下一个要检查的数是start+2（如果它在范围内）。
    // 但是，为了保持函数的通用性，并且展示递归的基本思想，这里我们还是每次检查start。
    // 在实际应用中，为了效率，可以改为每次增加2的步长，但那样就不是纯粹的“递归检查每个数”了。
    printOddNumbers(start + 1, end);
}

// 辅助函数，用于设置递归的起始和结束值，并调用递归函数
void printOddNumbersFrom1To100() {
    printOddNumbers(1, 101); // 注意：结束值设为101，因为范围是不包含结束值的
}

int main() {
    // 调用辅助函数打印1到100之间的所有奇数
    printOddNumbersFrom1To100();
    printf("\n"); // 打印换行符以美化输出
    return 0;
}

然而，上面的代码虽然展示了递归的基本思想，但它并不是最优的，因为对于每个数字（包括偶数），它都会执行一次模运算和一次条件判断。为了优化，我们可以稍微修改递归函数，使其直接跳过偶数，但这将改变递归函数的逻辑，使其不再检查每个数字是否为奇数。

为了保持递归的纯粹性并展示如何检查每个数字，同时为了提高效率（避免不必要的模运算），我们可以使用一个包装函数来启动递归，该函数从第一个奇数（即1）开始，并以2为步长递增递归函数中的起始值。但是，为了简洁和清晰，我将保持上面的代码不变，并指出在实际应用中，你可能会希望以不同的方式来实现这一点。

如果你想要一个更优化的版本，可以直接从1开始，每次递归调用时增加2，但那样就不是“检查每个数字是否为奇数”的递归示例了。下面的代码展示了这种优化方法：

#include <stdio.h>

// 优化后的递归函数，直接打印奇数序列中的下一个数
void printNextOddNumber(int current) {
    // 基本情况：如果当前数字大于100，则停止递归
    if (current > 100) {
        return;
    }
    // 打印当前奇数
    printf("%d ", current);
    // 递归调用，打印下一个奇数（current+2）
    printNextOddNumber(current + 2);
}

// 辅助函数，用于设置递归的起始值，并调用递归函数
void printOddNumbersFrom1To100Optimized() {
    printNextOddNumber(1); // 从第一个奇数开始
}

int main() {
    // 调用辅助函数打印1到100之间的所有奇数
    printOddNumbersFrom1To100Optimized();
    printf("\n"); // 打印换行符以美化输出
    return 0;
}

这个版本更加高效，因为它直接跳过了偶数，并且每次递归调用都增加了2。

写一个递归函数来打印1到100之间的奇数和，我们需要明确一点：打印和计算是两个不同的操作。如果你只是想打印出这些奇数的和（即一个总和数字），那么递归函数可以很简单。但如果你想要递归地打印出每个奇数，并且在最后打印出它们的总和，那么递归函数将需要一些额外的逻辑来累积和。

下面是一个C语言程序，它包含一个递归函数sumAndPrintOddNumbers，该函数不仅打印每个奇数，还在递归完成后打印它们的总和：

#include <stdio.h>

// 全局变量用于存储奇数的累积和
int oddSum = 0;

// 递归函数打印从start到end（不包含end）之间的所有奇数，并计算它们的和
void sumAndPrintOddNumbers(int start, int end) {
    // 基本情况：如果start大于或等于end，则停止递归
    if (start >= end) {
        return;
    }
    // 检查start是否为奇数
    if (start % 2 != 0) {
        // 打印当前奇数
        printf("%d ", start);
        // 累加当前奇数到全局变量oddSum
        oddSum += start;
    }
    // 递归调用，从start+1开始，但目标end不变
    sumAndPrintOddNumbers(start + 1, end);
}

// 辅助函数，用于设置递归的起始和结束值，并调用递归函数，最后打印总和
void printOddNumbersSumFrom1To100() {
    // 重置全局变量oddSum为0，以开始新的计算
    oddSum = 0;
    // 调用递归函数打印1到100之间的所有奇数，并计算它们的和
    sumAndPrintOddNumbers(1, 101); // 注意：结束值设为101，因为范围是不包含结束值的
    // 打印奇数的总和
    printf("\nSum of odd numbers from 1 to 100: %d\n", oddSum);
}

int main() {
    // 调用辅助函数
    printOddNumbersSumFrom1To100();
    return 0;
}

这个程序首先定义了一个全局变量oddSum来存储奇数的累积和。然后，sumAndPrintOddNumbers函数递归地检查每个数字是否为奇数，如果是，则打印它并累加到oddSum中。最后，printOddNumbersSumFrom1To100函数调用递归函数，并在递归完成后打印出奇数的总和。

1-100的奇数和

#include <stdio.h>

// 递归函数计算1到n的奇数之和
int sumOddRecursive(int n) {
    if (n <= 0) {
        return 0; // 确保n是正数
    } else if (n % 2 != 0) {
        return n + sumOddRecursive((n - 2)); // 如果n是奇数，返回n加上计算n-2的奇数和
    } else {
        return sumOddRecursive((n - 1)); // 如果n是偶数，则直接计算n-1的奇数和
    }
}

int main() {
    int sum = sumOddRecursive(100); // 计算1到100的奇数之和
    printf("Sum of odd numbers from 1 to 100: %d\n", sum); // 输出结果
    return 0;
}

薛老师总结：递归是计算机科学中一个非常强大且常见的概念，它涉及到函数调用自身来解决子问题。以下是一些递归相关的编程题目，涵盖了不同的难度级别和概念：

1.斐波那契数列：
编写一个递归函数来计算第n个斐波那契数。
优化递归算法，使用记忆化或动态规划减少重复计算。
2.阶乘：
编写一个递归函数来计算一个非负整数的阶乘。
3.汉诺塔问题：
编写一个递归函数来解决汉诺塔问题，并打印出每一步的移动。
4.树的遍历：
前序遍历、中序遍历和后序遍历的递归实现（针对二叉树）。
5.字符串反转：
编写一个递归函数来反转一个字符串。
6.数组求和：
编写一个递归函数来计算数组中所有元素的和。
7.数组的最大/最小值：
编写一个递归函数来找到数组中的最大值或最小值。
8.括号匹配：
编写一个递归函数来检查一个字符串中的括号是否匹配（考虑圆括号、方括号和花括号）。
9.路径问题：
在一个二维网格中，从左上角到右下角的路径有多少种（只能向右或向下移动）？
10.整数划分：
编写一个递归函数来计算将整数n划分为正整数和的不同方式的数量。
11.递归排序：
快速排序和归并排序的递归实现。
12.迷宫问题：
使用递归（可能结合回溯）来解决迷宫问题，找到从起点到终点的路径。
13.表达式求值：
编写一个递归函数来计算一个简单算术表达式的值（只包含加法和乘法）。
14.递归生成组合：
编写一个递归函数来生成从n个不同元素中取出k个元素的所有组合。
15.递归生成排列：
编写一个递归函数来生成n个不同元素的所有排列。
16.二叉搜索树的插入和查找：
使用递归来实现二叉搜索树的插入和查找操作。
17.递归删除二叉树节点：
编写一个递归函数来删除二叉树中的某个节点。
18.图的深度优先搜索（DFS）：
使用递归实现图的深度优先搜索。
19.图的广度优先搜索（BFS）（虽然通常使用队列实现，但理解递归与栈的关系也有助于理解BFS的递归版本）：
尝试使用递归（或栈模拟）来实现图的广度优先搜索。
20.约瑟夫问题：
编写一个递归函数来解决约瑟夫问题，即编号为1到n的人按指定的步长（m）进行报数并淘汰，直到最后一个人留下。
这些题目涵盖了递归在数据结构、算法和数学问题中的多种应用。通过解决这些问题，你可以更深入地理解递归的原理和技巧。