[C language] Analysis of function recursion (1)

作者:Mortal programming preach
系列:C语言初阶(适合小白入门)
说明:With the mortal ink,Writing big dreams of the future

₪前言

In this section, we study function recursive basic knowledge(The next section to start in-depth),The sections of content is a function of this chapter is the most important content,Even recursion in the later data structure and algorithm are applied to,So be sure to have a good grasp.好了,咱们直接进入主题.

₪什么是函数递归?

程序(函数)Call your programming skills is called recursive.递归作为一种算法在程序设计语言中广泛应用.一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,He is usually the problem of a complex huge layers into a similar to the original problem of smaller problems.递归的主要思考方式在于:把大事化小.

递归的两个必要条件

1. 递归存在限制条件,当满足这个限制条件的时候,递归便不再继续.
2. 每次递归调用之后越来越接近这个限制条件.

₪函数递归实例

例一

我们先来看一下,The most simple recursive code.

#include<stdio.h>
int main()
{
    
	printf("hehe\n");
	main();		//函数自己调用自己,也就是递归 
	return 0;
}

运行结果:

可以看到,This thought is infinite loop to printhehe,But an error.We might as well be debugged is wrong.

调试时,Program is directly the collapse,Visible to the problem of large.He report error is herestackoverflow(也就是栈溢出),As for what is a stack overflow,为什么会栈溢出？In this case, the first to sell a imprison son,In the next example explanation.

Through this example may know,We can have a look at our recursive code,是直接调用main()函数的,There is no restrictions(Also is the recursive function must satisfy the two conditions of),可以知道,As long as we don't meet the recursive two necessary conditions,Also can cause death recursive,从而导致栈溢出.

例二

题目:接收一个整形值(无符号),按照顺序打印他的每一位,例如输入1234,输出:1 2 3 4

分析：由题意可知,Is to let we enter an unsigned integer,And then enter it respectively every.Here loop with an array of course also can solve,But today's leading role is a recursive,Will use recursion to solve.首先,Recursion is the main ways of thinking of the big problem into a similar one by one small problem,So we print very quickly4个数.One can break up a print？Because we want to willo printed,So every time have to do is print a take a print,But because we want to order(从1开始),So let's be from1开始打印,The question to zha from1Start printing？Let's now is4位数,But we can always1234/10,In addition to the contractor1,And then began to print！At that time the za recursion condition came out,就是(假设1234为n) n>9(这个n>9Mean to2The number of digits or more),Then each recursive closer to don't meet this condition,知道这个n<=9时,也就是n==1Begin printing.

I know a lot of the above said sure you still don't understand,It doesn't matter directly look at the following code and I diagram can understand！

代码如下:

#include<stdio.h>
void print(int k)
{
    
	if (k > 9)
	{
    
		print(k / 10);
	}
	printf("%d ", k % 10);
}
int main()
{
    
	int n;
	scanf("%d", &n);		//输入1234
	print(n);	//递归函数
	return 0;
}

运行结果:

来,Don't understand the classmate see this picture.

例三(栈溢出原因)

我们上面说了,Function recursive two conditions must be met,A limited condition,2 it is recursive every time close to this condition.If there is no this condition will stack overflow,So is there the two conditions do not stack overflow？

看代码:

#include<stdio.h>
void test(int i)
{
    
	if(i<10000)
	{
    
		test(i+1);		
	}
}
int main()
{
    
	test(1);
	return 0;
}

You can see recursive constraints isi<10000,And every time when recursivei+1,越来越接近这个条件.

运行结果:

可以看到,Even with the two necessary conditions for,Also will stack overflow.那么是为什么呢？

We first introduce the memory layout:

And every time the function call,Will be on the stack area opened up a piece of memory space,而这里的testFunction recursive condition isi<10000,Every time a recursive isi+1,Equivalent to a recursive10000-1次,So every time want to call this recursive function,Stack the memory space is limited,So finally the results of this code is a stack overflow.

如图所示

所以,If we only guarantee the two necessary conditions is not enough,And ensure that every time the level of the recursive don't deep,To prevent memory space runs out.

₪结言

好了,The content of the section is the,希望对你有收获,The next section, we better！下一节见！