Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

C allows functions to call themselves, and this call is called recursion. A lot of people, when they first start learning recursion, get confused by the layers of nested calls, how do you call them? Here is a small example of how a function works when called recursively.

void up_and_down(int n)
{
	printf("---- Level %d: n location 0x%p \r\n",n,&n);
	if(n<4)
		up_and_down(n + 1);
	printf("**** Level %d: n location 0x%p \r\n",n,&n);
}
int main(a)
{
	up_and_down(1);
	
	system("pause");
	return 0;
}
Copy the code

First call the function to assign n to 1, then add 1 to n when n is less than 4, and then continue calling the function. Exit the function until n is greater than 4.

It can be seen from the printed result that the value of n increases successively from 1, 2, 3 and 4, and then decreases successively from 4, 3, 2 and 1, and finally exits the program. So what is the process of this program? Here’s a picture to analyze.

Here’s a step by step analysis:

First n=1, execute the first print statement in the function body. It then executes the if statement, and since n is currently 1 and less than 4, it calls the function itself, passing the value of 1+1 to the function.

Next, execute the first print statement in the function body. It then executes the if statement, and since n is currently 2 and less than 4, it calls the function itself, passing the value of 2+1 to the function.

Proceed with the first print statement in the function body. It then executes the if statement, and since n is currently 3 and less than 4, it calls the function itself, passing the value of 3+1 to the function.

Proceed with the first print statement in the function body. It then executes the if statement, and since n is currently 4, not less than 4, the if condition is not true. It does not call up_and_down () anymore, but executes the last print statement in the function body. When the print statement is finished, exit the function. Since the fourth call is from the third call, the program returns to where it was called the third time after exiting the fourth call.

The up_and_down(3 + 1) of the third function is returned after the fourth exit. At this point, since the function has already been executed, the code continues, printing the last line of the print statement.

Again, when the third function is finished, the program returns to where it was called, that is, to the function called the second time.

The program returns up_AND_down (2 + 1); After this statement, proceed to the print statement on the last line. When the print statement on the last line completes, the function called the second time returns to where it was called, inside the function called the first time.

The program returns up_and_down(1 + 1); After this statement, proceed to the print statement on the last line. When the last line of print completes, the program returns to where the function was first called. The first time this function is called is inside main(), so the program will fall back inside main(). No other statements are executed in the main() function. So the whole process of the program is finished.

As can be seen from the printed result, the first print statement is the first line in the function body. After all four function calls are completed, the last print statement in the function body is continued. Each time a new function is called, a new address is assigned to n, and when the function exits, the new address is released.

It can be seen that the recursive function in the execution of the time, or a waste of memory space, for the resources of the microcontroller is very limited, or as little as possible to use the recursive function. Do recursive functions really have no advantage at all? Of course, there is, through the above example observation can be found, recursive functions are first in last out principle, so for the need to reverse execution of the program, using recursive functions is very convenient. For example, when performing base conversion, the first computed value is placed in the last digit of the result, and the last computed value is placed in the first digit of the result.

Let’s say we want to convert 10 to binary. The calculation process is as follows:

2-0 10%

10/2 = 5

2 — — — — — 1 5%

5/2 = 2

2-0 2%

2/2 = 1

2 — — — — — 1 1%

You divide 10 by 2 and you take the remainder, and the remainder is 0, so that 0 is the least significant binary base. And then you divide 10 by 2, and then you divide it by 2, and you mod it, and that’s the second to last binary, and you do that, and you do that until you get 1.

That is, when the passed argument becomes 1, the recursive call ends. So 10 is converted to binary as 1010, which happens to be the calculated number in reverse order.

Let’s do this recursively

void to_binary(unsigned long  n)
{
	int r;
	r = n % 2;
	if(n >= 2)
		to_binary(n/2);
	putchar(r == 0?'0':'1');
	return;
}
int main(a)
{
	to_binary(100);
	printf("\r\n");
	system("pause");
	return 0;
}
Copy the code

Define a function to print a binary value by dividing the number by 2, and then calling the function after dividing the number by 2.

Convert 100 to a binary value

The result printed by the program is the same as the result calculated in practice, indicating that the program function is normal. You can print out the execution of the function for easy viewing.

To check the efficiency of the function, you can print the time of the function execution. The test code is as follows:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
void to_binary(unsigned long  n)
{
	int r;
	r = n % 2;
	printf("n-%d,r-%d\r\n",n,r);
	if(n >= 2)
		to_binary(n/2);
	putchar(r == 0?'0':'1');
	return;
}
typedef union _LARGE_INTEGER
{
	struct
	{
		long LowPart ;// A 4-byte integer
		long  HighPart;// A 4-byte integer
	};
	long long QuadPart;// An 8-byte integer
 
} LARGE_INTEGER; 
 
int main(int argc, char *argv[])
{
	int i = 0,val = 0;
	clock_t startTime,endTime;
	int time = 0;
	
	LARGE_INTEGER secondcount= {0};
	LARGE_INTEGER startcount= {0};
	LARGE_INTEGER stopcount= {0};
 
	QueryPerformanceFrequency(&secondcount);     // Obtain the number of CPU Performance Tick units per second
	//printf(" 3: system count frequency: %d \r\n", secondCount.QuadPart);
 
	QueryPerformanceCounter(&startcount);		// Start the timer
	to_binary(100);					// recursive call
	QueryPerformanceCounter(&stopcount);		// The timer ends
	
	time=( ((stopcount.QuadPart - startcount.QuadPart)*1000*1000)/secondcount.QuadPart);
	printf("\r\n\r\n program run time: %d us\r\n\r\n",time);
 
	system("pause");
	return 0;
}
Copy the code

Here added a test recursive call function execution time, the principle of the test is, before the function execution record the system count value, and then after the completion of the execution, record the system statistics value, the difference between the two values is the system execution time. The result is as follows:

You can see that it takes 1.163ms to compute a binary number of 100 once, which is too slow for a computer. Wouldn’t it take more time to calculate a larger number, so let’s test it out with the number 10,000,000.

It takes about 5.1ms, so the larger the number, the deeper the function is nested, and the more memory it consumes. The longer it takes to execute.

When using recursive functions in the future, we must pay attention to the use of the environment, otherwise, if we call a nested recursive function on a single chip microcomputer with fewer resources, it is likely that the system resources will be exhausted in half, resulting in program crash, and it is difficult to find the cause.