Programming learning records - Lesson 7 [functions]

Function declaration

1. Tell the compiler that there is a function called , What are the parameters , What is the return type . But does it exist , function

The statement does not determine .

2. The declaration of a function usually precedes the use of the function . To satisfy the requirement of declaration before use .

3. The declaration of the function is usually placed in the header file .

Function definition

The definition of a function refers to the concrete implementation of a function , Explain the function realization .

Recursion of a function

A procedure or function has a method that directly or indirectly calls itself in its definition or description , Usually, a large and complex problem can be transformed layer by layer into a smaller problem similar to the original problem to solve , Recursion can simplify and reduce the number of program code , But it may also increase the amount of computation .

Two necessary conditions for recursion

1. Recursion requires restrictions , When the conditions are met , Recursion doesn't continue , Recursion cannot go on indefinitely , Otherwise, it will cause dead loop and stack overflow .

2. With recursive execution , Getting closer to the constraints .

recursive thinking

Break down the problem , From big to small .

Example 1： Enter an integer , Print each digit of the integer in turn .

The idea is , Divide the integer by an integer , For example, the input 1234, hold 1234 delimit 123, Print 4, And then 123 delimit 12, Print 3, hold 12 delimit 1 and 2, Print 2, Re print 1.

Realization ：

void print(int n)
{
	if (n > 9)
	{		
    print(n / 10);
	}
	printf("%d ", n % 10);
}

Example 2： Without creating temporary variables , Find the length of a string array .

First , The parameter passed to the function by string array is the pointer address of the first element of an array ,

We can control the pointer to move to the right , Until the element pointed to by the pointer is the termination symbol of the string array '\0', It means to the far right of the array .

Realization :

int strlen(char* sz)
{
	if (*sz != '\0')
	{
		return 1 + strlen(sz + 1);
	}
	else return 0;
}

Example 3： Reverse a string array .

To reverse the order , We can start from both sides of the array , Swap the first and last elements of the array . Then swap the rest of the string array , Until the remaining array length is less than 2 Stop when .

Realization ：

void reverse_string(char* string)// Pass pointer to function parameter , The first thing passed is the pointer to the first element of the array .
{
	int n = strlen(string);// According to the example 2, Find the length of the current array 
	char frist = *string; // Assign the first element of the current array to frist
	*string = *(string + n - 1); // Put the last element of the current array first .
	*(string + n - 1) = '\0';	// Temporarily reduce the length of the array 
    if(strlen(string)>2) // When the array length is greater than 2 when   Recursion .
	{
		reverse_string(string + 1);
	}
	*(string + n - 1) = frist; Place the first element at the end of the current array .
}

Example 4：

When we use recursive method to calculate Fibonacci sequence , You will find that when the number of sequences is large , The calculation will be slow or even crash , This is because when calculating Fibonacci sequence with recursive method , There are many repeated calculations , Wasted time .

Compare ：

// Fibonacci sequence - recursive 
int function1(int n)
{
	if (n <= 2) return 1;
	else return function1(n - 1) + function1(n - 2);
}
// Fibonacci sequence - Not a recursive 
int function2(int n)
{
	int f1 = 1;int f2 = 1;int f3 = 0;
	if (n <= 2) return 1;
	else 
	{
		for (int i = 2;i < n;i++)
		{
			f3 = f1 + f2;
			f1 = f2;
			f2 = f3;
		}
		return f3;
	}
}

You can see , When using recursion , The code is more concise , But the corresponding , Will increase repeated calculations .