06_C基础(循环与递归、printf)

科锐c语言教程

循环结构和递归

递归

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

基准情况：这是递归结束的条件。当满足基准情况时，函数不再调用自身，而是直接返回一个结果。基准情况确保递归不会无限进行下去，从而防止堆栈溢出。
递归情况：这是函数调用自身的部分。在递归情况中，函数会分解问题，并调用自身来解决分解后的小问题。

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

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)时，函数执行如下步骤：

factorial(5)调用factorial(4)
factorial(4)调用factorial(3)
factorial(3)调用factorial(2)
factorial(2)调用factorial(1)
factorial(1)返回1

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

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

循环结构与递归对比

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

循环结构

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

优点：

效率高：循环通常比递归更高效，因为它们不需要函数调用的额外开销。
简单易懂：对于简单的重复任务，循环结构更加直观明了。
低内存消耗：循环使用的内存较少，不会像递归那样消耗堆栈空间。

缺点：

灵活性有限：在处理一些需要分解成更小问题的复杂任务时，循环可能不如递归直观。
代码可能较冗长：在某些情况下，循环结构可能需要更多的代码来处理边界情况和维护状态。

示例：计算阶乘

#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;
}

递归

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

优点：

简洁优雅：对于一些自然递归的问题（如树结构、图算法等），递归解决方案通常更加简洁和易于理解。
代码结构清晰：递归代码通常更具结构性，易于维护和扩展。
适用于分治法：递归非常适合分治算法，将大问题分解成小问题。

缺点：

性能较低：递归函数调用有额外的开销，可能导致性能下降。
容易造成堆栈溢出：如果递归深度太大，可能导致堆栈溢出。
复杂性增加：有些递归问题可能需要复杂的思维方式来理解和调试。

示例：计算阶乘

#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;
}

对比总结

效率：循环结构一般比递归更高效，特别是在需要大量迭代的情况下。
可读性：递归在处理某些问题时更为自然和简洁，但对于不熟悉递归的人来说，可能不如循环直观。
适用性：循环适用于简单的重复任务，递归适用于分解问题或处理递归结构的数据（如树和图）。

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

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;
}

详细解释

整数格式化

%d、%i：以十进制格式输出有符号整数。
%u：以十进制格式输出无符号整数。
%x、%X：以十六进制格式输出无符号整数。
%o：以八进制格式输出无符号整数。

浮点数格式化

%f：以浮点数格式输出。
%e、%E：以科学记数法格式输出。
%g、%G：根据数值的大小选择%f或%e（%E）格式输出。

字符串和字符格式化

%s：输出字符串。
%c：输出单个字符。

特殊格式化

%p：输出指针地址。
%n：将当前已输出的字符数存入参数指向的整数变量中。
%%：输出一个百分号。

转义字符

常见转义字符

\a：响铃（警报）
\b：退格
\f：换页
\n：换行
\r：回车
\t：水平制表符（tab）
\v：垂直制表符
\\：反斜杠
\'：单引号
\"：双引号
\?：问号
\0：空字符（Null字符）

其他转义序列

\nnn：三位八进制数表示的字符，例如\101表示字符A。
\xhh：两位十六进制数表示的字符，例如\x41表示字符A。
\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;
}

详细解释

递归基准情况：

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

递归情况：

对于 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，可以考虑使用动态规划或迭代方法来优化计算。

如果觉得文章对你有用，请随意赞赏

06_C基础(循环与递归、printf)

https://www.kiciot.com/archives/06CBasicLoopRecursionPrintf

作者

Administrator

发布于

2024-09-28

更新于

2024-09-28

许可协议

CC BY 4.0

06_C基础(循环与递归、printf)

循环结构和递归

递归

循环结构与递归对比

循环结构

递归

对比总结

Printf

基本格式

格式说明符

1. flags（标志）

2. width（宽度）

3. precision（精度）

4. length（长度）

5. specifier（转换说明符）

示例

详细解释

转义字符

常见转义字符

其他转义序列

递归斐波那契数列

详细解释

示例输出

注意事项

作者

发布于

更新于

许可协议

评论