06_C基础(循环与递归、printf)
循环结构和递归
递归
递归是一种编程技术,通过函数调用自身来解决问题。递归的核心思想是将一个复杂问题分解成更小的相同问题,然后递归地解决这些小问题。递归通常包括两个部分:基准情况和递归情况。
基准情况:这是递归结束的条件。当满足基准情况时,函数不再调用自身,而是直接返回一个结果。基准情况确保递归不会无限进行下去,从而防止堆栈溢出。
递归情况:这是函数调用自身的部分。在递归情况中,函数会分解问题,并调用自身来解决分解后的小问题。
以下是一个经典的递归例子:计算阶乘。
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
。\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;
}
详细解释
递归基准情况:
当
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)
返回 1fibonacci(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
,可以考虑使用动态规划或迭代方法来优化计算。