循环结构和递归

递归

递归是一种编程技术，通过函数调用自身来解决问题。递归的核心思想是将一个复杂问题分解成更小的相同问题，然后递归地解决这些小问题。递归通常包括两个部分：基准情况和递归情况。

1. 基准情况：这是递归结束的条件。当满足基准情况时，函数不再调用自身，而是直接返回一个结果。基准情况确保递归不会无限进行下去，从而防止堆栈溢出。

2. 递归情况：这是函数调用自身的部分。在递归情况中，函数会分解问题，并调用自身来解决分解后的小问题。

以下是一个经典的递归例子：计算阶乘。

def factorial(n):
    if n == 1:  # 基准情况
        return 1
    else:
        return n * factorial(n - 1)  # 递归情况

在这个例子中：

• 基准情况是if n == 1，当n等于1时，函数返回1。

• 递归情况是n * factorial(n - 1)，函数调用自身来计算n - 1的阶乘。

当我们调用factorial(5)时，函数执行如下步骤：

1. factorial(5)调用factorial(4)

2. factorial(4)调用factorial(3)

3. factorial(3)调用factorial(2)

4. factorial(2)调用factorial(1)

5. factorial(1)返回1

然后，每次调用返回的值乘以当前的n，直到最终返回结果：

factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24
factorial(5) = 5 * 24 = 120

循环结构与递归对比

循环结构和递归是两种常见的控制流结构，它们在解决问题时各有优缺点。以下是它们的对比：

循环结构

定义：通过重复执行一组语句，直到满足特定条件为止。

优点：

1. 效率高：循环通常比递归更高效，因为它们不需要函数调用的额外开销。

2. 简单易懂：对于简单的重复任务，循环结构更加直观明了。

3. 低内存消耗：循环使用的内存较少，不会像递归那样消耗堆栈空间。

缺点：

4. 灵活性有限：在处理一些需要分解成更小问题的复杂任务时，循环可能不如递归直观。

5. 代码可能较冗长：在某些情况下，循环结构可能需要更多的代码来处理边界情况和维护状态。

示例：计算阶乘

#include <iostream>
using namespace std;

int factorial_iterative(int n) {
    int result = 1;
    for (int i = 1; i <= n; ++i) {
        result *= i;
    }
    return result;
}

int main() {
    int number = 5;
    cout << "Factorial of " << number << " is " << factorial_iterative(number) << endl;
    return 0;
}

递归

定义：函数通过调用自身来解决问题，通常包括基准情况和递归情况。

优点：

1. 简洁优雅：对于一些自然递归的问题（如树结构、图算法等），递归解决方案通常更加简洁和易于理解。

2. 代码结构清晰：递归代码通常更具结构性，易于维护和扩展。

3. 适用于分治法：递归非常适合分治算法，将大问题分解成小问题。

缺点：

4. 性能较低：递归函数调用有额外的开销，可能导致性能下降。

5. 容易造成堆栈溢出：如果递归深度太大，可能导致堆栈溢出。

6. 复杂性增加：有些递归问题可能需要复杂的思维方式来理解和调试。

示例：计算阶乘

#include <iostream>
using namespace std;

int factorial_recursive(int n) {
    if (n == 1) {
        return 1;
    } else {
        return n * factorial_recursive(n - 1);
    }
}

int main() {
    int number = 5;
    cout << "Factorial of " << number << " is " << factorial_recursive(number) << endl;
    return 0;
}

对比总结

19. 效率：循环结构一般比递归更高效，特别是在需要大量迭代的情况下。

20. 可读性：递归在处理某些问题时更为自然和简洁，但对于不熟悉递归的人来说，可能不如循环直观。

21. 适用性：循环适用于简单的重复任务，递归适用于分解问题或处理递归结构的数据（如树和图）。

选择使用循环还是递归，取决于具体问题的性质和个人对代码可读性与效率的需求。

Printf

基本格式

printf("format string", argument_list);

• format string：格式字符串，包含普通字符和格式说明符。

• argument_list：对应格式说明符的参数列表。

格式说明符

格式说明符以百分号（%）开头，后面跟随以下元素来定义输出格式：

%[flags][width][.precision][length]specifier

1. flags（标志）

• -：左对齐，右侧填充空格。

• +：输出正数时加正号。

• 空格：输出正数时加空格。

• #：对不同数据类型有不同含义，例如，输出八进制时加前缀0，输出十六进制时加前缀0x或0X。

• 0：在指定宽度内，数字前面补零。

2. width（宽度）

• 数字：最小输出宽度。

• *：从参数列表中读取宽度值。

3. precision（精度）

• .数字：对于浮点数，表示小数点后的位数；对于字符串，表示最大输出字符数。

• .*：从参数列表中读取精度值。

4. length（长度）

• h：短整型（short int）。

• hh：字符型（char）。

• l：长整型（long int）。

• ll：长长整型（long long int）。

• j：intmax_t类型。

• z：size_t类型。

• t：ptrdiff_t类型。

• L：长双精度（long double）。

5. specifier（转换说明符）

• d、i：有符号十进制整数。

• u：无符号十进制整数。

• f：浮点数（十进制记数法）。

• e、E：浮点数（科学记数法）。

• g、G：自动选择f或e（或E）格式。

• x、X：无符号十六进制整数。

• o：无符号八进制整数。

• s：字符串。

• c：字符。

• p：指针地址。

• n：存储到目前为止输出的字符数。

• %：输出一个百分号。

示例

#include <stdio.h>

int main() {
    int i = 123;
    double d = 123.456;
    char *s = "Hello, world!";

    // 基本示例
    printf("%d\n", i);  // 输出：123
    printf("%10d\n", i);  // 输出：       123
    printf("%-10d\n", i);  // 输出：123       
    printf("%010d\n", i);  // 输出：0000000123

    // 浮点数
    printf("%f\n", d);  // 输出：123.456000
    printf("%.2f\n", d);  // 输出：123.46
    printf("%10.2f\n", d);  // 输出：    123.46

    // 字符串
    printf("%s\n", s);  // 输出：Hello, world!
    printf("%.5s\n", s);  // 输出：Hello

    return 0;
}

详细解释

1. 整数格式化

• %d、%i：以十进制格式输出有符号整数。

• %u：以十进制格式输出无符号整数。

• %x、%X：以十六进制格式输出无符号整数。

• %o：以八进制格式输出无符号整数。

1. 浮点数格式化

• %f：以浮点数格式输出。

• %e、%E：以科学记数法格式输出。

• %g、%G：根据数值的大小选择%f或%e（%E）格式输出。

1. 字符串和字符格式化

• %s：输出字符串。

• %c：输出单个字符。

1. 特殊格式化

• %p：输出指针地址。

• %n：将当前已输出的字符数存入参数指向的整数变量中。

• %%：输出一个百分号。

转义字符

常见转义字符

• \a：响铃（警报）

• \b：退格

• \f：换页

• \n：换行

• \r：回车

• \t：水平制表符（tab）

• \v：垂直制表符

• \\：反斜杠

• \'：单引号

• \"：双引号

• \?：问号

• \0：空字符（Null字符）

其他转义序列

• \nnn：三位八进制数表示的字符，例如\101表示字符A。

• \xhh：两位十六进制数表示的字符，例如\x41表示字符A。

• \uhhhh：四位十六进制数表示的Unicode字符（C++11及以上支持），例如\u00A9表示©。

• \Uhhhhhhhh：八位十六进制数表示的Unicode字符（C++11及以上支持），例如\U0001F600表示😀。

递归斐波那契数列

• F(0) = 0

• F(1) = 1

• 对于 n >= 2，F(n) = F(n-1) + F(n-2)

使用递归可以很自然地实现这个数列。以下是用C++实现斐波那契数列的递归版本：

#include <iostream>
using namespace std;

// 递归函数计算斐波那契数
int fibonacci(int n) {
    if (n == 0) {
        return 0;  // 基准情况1
    } else if (n == 1) {
        return 1;  // 基准情况2
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);  // 递归情况
    }
}

int main() {
    int n;
    cout << "Enter a positive integer: ";
    cin >> n;
    cout << "Fibonacci(" << n << ") = " << fibonacci(n) << endl;
    return 0;
}

详细解释

1. 递归基准情况：

• 当 n == 0 时，返回 0。

• 当 n == 1 时，返回 1。

2. 递归情况：

• 对于 n >= 2，函数调用自身来计算 fibonacci(n-1) 和 fibonacci(n-2)，然后将这两个结果相加。

示例输出

假设用户输入 5，执行过程如下：

• fibonacci(5) 需要 fibonacci(4) 和 fibonacci(3)

• fibonacci(4) 需要 fibonacci(3) 和 fibonacci(2)

• fibonacci(3) 需要 fibonacci(2) 和 fibonacci(1)

• fibonacci(2) 需要 fibonacci(1) 和 fibonacci(0)

• fibonacci(1) 返回 1

• fibonacci(0) 返回 0

这会导致函数调用链如下：

fibonacci(5)
|
+-- fibonacci(4)
|   |
|   +-- fibonacci(3)
|   |   |
|   |   +-- fibonacci(2)
|   |   |   |
|   |   |   +-- fibonacci(1) -> 1
|   |   |   +-- fibonacci(0) -> 0
|   |   +-- fibonacci(1) -> 1
|   +-- fibonacci(2)
|       |
|       +-- fibonacci(1) -> 1
|       +-- fibonacci(0) -> 0
+-- fibonacci(3)
    |
    +-- fibonacci(2)
    |   |
    |   +-- fibonacci(1) -> 1
    |   +-- fibonacci(0) -> 0
    +-- fibonacci(1) -> 1

最后结果为 fibonacci(5) = 5。

注意事项

虽然递归实现斐波那契数列非常直观，但其时间复杂度为O(2^n)，效率较低。对于较大的 n，可以考虑使用动态规划或迭代方法来优化计算。