1.什么是递归?
程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中广泛应用。
一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。
递归的主要思考方式在于:把大事化小
2.递归的两个必要条件
存在限制条件,当满足这个限制条件的时候,递归便不再继续。每次递归调用之后越来越接近这个限制条件。
编写一个函数 reverse_string(char * string)(递归实现)
实现:将参数字符串中的字符反向排列,不是逆序打印。
要求:不能使用C函数库中的字符串操作函数。
比如:char arr[] = "abcdef";
逆序之后数组的内容变成:fedcba
/*
思路:
逆置字符串,循环的方式实现非常简单
1. 给两个指针,left放在字符串左侧,right放在最后一个有效字符位置
2. 交换两个指针位置上的字符
3. left指针往后走,right指针往前走,只要两个指针没有相遇,继续2,两个指针相遇后,逆置结束
*/
void reverse_string(char* arr)
{
char* left = arr;
char* right = arr + strlen(arr) - 1;
while (left < right)
{
char tmp = *left;
*left = *right;
*right = tmp;
left++;
right--;
}
}
/*
递归方式:
对于字符串“abcdefg”,递归实现的大概原理:
1. 交换a和g,
2. 以递归的方式逆置源字符串的剩余部分,剩余部分可以看成一个有效的字符串,再以类似的方式逆置
*/
void reverse_string(char* arr)
{
int len = strlen(arr);
char tmp = *arr;
*arr = *(arr + len - 1);
*(arr + len - 1) = '\0';
if (strlen(arr + 1) >= 2)
reverse_string(arr + 1);
*(arr + len - 1) = tmp;
}