[C language] Analysis of function recursion (2)

作者:凡人编程传
系列:C语言初阶(适合小白入门)
说明:以凡人之笔墨,书写未来之大梦

₪前言

In this section, we continue to talk about the content of function recursion,Learn more about how recursion actually works,好了,咱们直接进入正题.

₪自定义实现strlen函数(不能创建临时变量)

Maybe some people don't know yet strlen函数是啥,It doesn't matter, let's open it firstMSDN查一查.

由图可知,The function of this function is to get the length of a string.And the header file he belongs to is< string.h >,返回类型是size_t（It is unsigned integer）,参数是const char*string,这里的const以后会讲,Let's pretend he doesn't exist.好了,Know the basic situation of this function,Come and use it.

#include<stdio.h>
#include<string.h>
int main()
{
    
	char arr[] = "bit";
	int len = strlen(arr);		//The array name here,相当于数组首元素地址,也就是char* arr
	printf("len = %d", len);
	return 0;
}

这里补充一点,Every string has an end character’\0’,而strlen()The function just encounters this end character and stops counting how many characters there are(不包括\0).

如bitThis string is stored in the array as shown in the figure:

运行结果:

所以strlen函数遇到\0就停止计数,那么\0之前就有3个字符,也就是3.

So let's implement this function ourselves now,Let's not create temporary variables according to the topic.Know from the above,The biggest feature of this function is encounter\0It starts not counting.Then we can use this as the loop count condition,We pass the address of the first element of the array,然后每次* Dereference to see if the element in this address is\0,If not, it means that the string has at least one character,Then our count variable will auto-increment and record that the string has one character,Until the content inside the address is dereferenced once\0Indicates the end of this string,后面没有字符了.Then the length of the final count variable is the length of the string.

代码如下:

#include<stdio.h>
int my_strlen(char* str)
{
    
	int count = 0;	//计数变量
	while (*str != '\0')		//如果strThe contents of the address pointed to by the pointer are not\0,Then the representative string is not over yet
	{
    
		count++;	//不是\0represents a character,记录字符个数
		str++;		//指针指向下一个地址
	}
	return count;
}
int main()
{
    
	char arr[] = "bit";
	int len = my_strlen(arr);		//The array name here,相当于数组首元素地址,也就是char* arr
	printf("len = %d", len);
	return 0;
}

运行结果:

虽然结果是正确的,But we don't fit the purpose.Question Let's not create temporary variables.那么我们怎么改呢？唉,We're talking about recursion in this section!It must be written recursively！没错,We just use recursion.

We are recalling the two necessary conditions and ideas of recursion
一、 递归的两个必要条件:
1.递归一定要有限制条件
2.Each recursion gets closer and closer to this limit

二、 递归的思考方式:
把大问题,Divide it into small problems similar to the original problem.

In fact, the word recursion can reflect his algorithm,"递"It's the deepest first,“归"That is, from the deepest to the shallowest,That is, counting from the back to the front.So we can find it first\0,让后\0开始"归”.Two points should be noted here：If our string is not the empty string then the number of characters is at least1吧,The case if the string is the empty string(That is, there is only one in it\0),So when writing, be sure to consider the case of empty strings.那么就可以写代码了:

代码如下:

#include<stdio.h>
int my_strlen(char* str)
{
    
	
	if (*str != '\0')		//如果strThe contents of the address pointed to by the pointer are not\0,Then the representative string is not over yet
	{
    
		return 1 + my_strlen(str + 1);		//If the content inside the address is not\0,Then it means that there is at least one character1+... ,Also our purpose is to find first\0Then count from back to front
	}
	else
	{
    
		return 0;		//empty string case
	}
}
int main()
{
    
	char arr[] = "bit";
	int len = my_strlen(arr);		//The array name here,相当于数组首元素地址,也就是char* arr
	printf("len = %d", len);
	return 0;
}

运行结果:

如果还是不懂,It's okay, please look at this picture:

Two points should be emphasized here：
1.One is thatelse情况的return 0一定要写,Even if you don't consider the case of empty strings, if you don't write it, the result will be wrong,因为递归"'归"When there must be a return value,If not write thatelse返回一个0,Then the compiler will automatically return a random value to you,那么后面1+…When the value will be wrong.
2.The second is that someone is sure to want to know thatstr+1,能不能写成str++,It's very clear that you can't,Because what we want is the address next to the current address,如果你写成str++If so, it is the originalstr的地址,Then passedstr的地址再+1(后置自增,先引用,再自增),Then there is a conflict!

₪结言

由于时间关系,I was going to finish it all,但是太忙了,We will add the last two questions tomorrow,Please understand here,Well, hope it works for you,下一节见！