[function explanation (Part 2)] | [function declaration and definition + function recursion] key analysis + code diagram

 

 

Catalog

Function declaration and definition

Tool Manual —— Function declaration

Production tools —— Function definition

Advantages of writing functions in modules

  Function recursion

Two necessary conditions for recursion

practice 1： Accept an integer value （ Unsigned ）, Print each bit of it in order .

practice 2： Writing functions does not allow the creation of temporary variables , Find the length of the string .

  practice 3： seek n The factorial .（ Don't think about spillovers ）

practice 4： Please n Fibonacci Numbers .

The fatal flaw of recursive functions ： Huge overhead of memory and time

Improve and optimize

---

Function declaration and definition

The declaration of a function is very similar to the definition of a function , But they are fundamentally different . Declaration does not open up memory , Just tell the compiler , The part to declare exists , Leave a little space . Definition requires opening up memory .

Tool Manual —— Function declaration ：

C Language code is executed from top to bottom , In principle, the function definition should appear before the function call , Just like variables , I need to define a variable first , Use variables again , Otherwise you will report an error . But in real development , They are often used before functions are defined , It's time to make a statement in advance .

1. Function declaration is to tell the compiler what a function is called , What are the parameters , What is the return type , But whether there is , Be of no great importance , But please don't report an error , I'll fill in the definition later .

2. Function declarations usually appear before function calls , To meet the Declare before use .

3. Function declarations are usually placed in The header file in .

Format ：

Return type     Function name （ Parameters 1 type Parameters 1, Parameters 2 type Parameters 2,……）;

int Add(int x,int y);

Production tools —— Function definition ：

If you compare function declarations to “ Instructions for tools ”, The function definition is equivalent to making this tool . Function definition is the concrete implementation of a function , The function realization of the replacement function . In the program , A function can only be defined once .

Format ：

  Return type     Function name （ Parameters 1 type Parameters 1, Parameters 2 type Parameters 2,……）
 {
      The body of the function ······
 }

int Add(int x,int y)
{
    return x+y;
}

---

  In our textbooks , Implement a function as shown in the figure below ：

  But when we realize the project , Implementing a function is written in multiple modules ：

1. Let's create a source file and a header file respectively , Named as Add.c and Add.h

2. Put the function declaration into the header file Add.h in , Put the function definition into the source file Add.c in .

3.Add.c and Add.h Together, it is an addition module , Including function declaration and function definition , In the future, when adding functions are used , as long as #include"Add.h" that will do .

  

The program is generated by compiling each source file into .obj, Then put a few more .obj Link generator .
As long as a function is declared in a source file , It can be compiled into .obj, Function definitions are bound only when linking .
So you can put it in the source file test.c Pass through ##include"Add.h" Declare a function , stay Add.c It defines （ Realization ） it . such ,test.c and Add.c It's connected . As shown in the figure ：

Advantages of writing functions in modules ：

1. You can collaborate with many people , A clear division of responsibilities , high efficiency .

2. It can realize encapsulation and hiding

for instance A The company has developed a complex function , It can be sold to other companies for their use , however A The company doesn't want to implement all the functions （Add.c) Sell it out , The company just wants to sell this function for the first time , Realize annual charging . So you can encapsulate and hide functions .

for example A The company developed a Add function

 A The company only Add.h and Add.lib Sell to other companies

 

 

---

  Function recursion

A function called in its function body is called itself Recursively call , This function is called Recursive function . Executing a recursive function will call itself repeatedly , Each call enters a new layer , When the innermost function is executed , Exit layer by layer from the inside to the outside .

It usually puts a large complex Miscellaneous problems are transformed into one A smaller problem similar to the original problem To solve , The recursive strategy requires only a small number of programs Describe the multiple repetitions required to solve the problem , Greatly reduces the amount of code in the program . The main way of thinking about recursion is On ： Turn the big thing into a small one .

Two necessary conditions for recursion

1. There are restrictions , When this constraint is met , Recursion doesn't continue .

2. After each recursive call, it gets closer and closer to this constraint .

practice 1： Accept an integer value （ Unsigned ）, Print each bit of it in order .

Print(unsigned int num)
{
	if (num > 9)
	{
		Print(num / 10);
	}
	printf("%d ", num % 10);
}
int main()
{
	unsigned int num = 1234;
	Print(num);
	return 0;
}

 

practice 2： Writing functions does not allow the creation of temporary variables , Find the length of the string .

int my_strlen(char *p)
{
	if (*p != '\0')
	{
		return 1 + my_strlen(p + 1);
	}
	else return 0;	
}
int main()
{
	char arr[] = "abcd";
	
	int len=my_strlen(arr);
	printf("%d\n", len);
	return 0;
}

  practice 3： seek n The factorial .（ Don't think about spillovers ）

int fac(int n)
{
	if (n == 1 || n == 0)
	{
		return 1;
	}
	else
		return fac(n - 1)*n;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	fac(n);
	return 0;
}

practice 4： Please n Fibonacci Numbers .

int fib(int n)
{
	if (n <= 2)
	{
		return 1;
	}
	else
	{
		return fib(n - 2) + fib(n - 1);
	}
}
	int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret=fib(n);
	printf("%d\n",ret);
	return 0;
}

 

  But we found something wrong ;

1. In the use of fib When we use this function, if we want to calculate the number 50 A Fibonacci number is particularly time-consuming .

2. Use fac Function finding 10000 The factorial （ Regardless of the correctness of the results ）, The program will crash .

The fatal flaw of recursive functions ： Huge overhead of memory and time

 

 

 

Improve and optimize ：

int fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = fib(n);
	printf("%d\n", ret);

	return 0;
}

int fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = fib(n);
	printf("%d\n", ret);

	return 0;
}

Tips ：

1. Many problems are explained recursively , This is only because it is clearer than the non recursive form .

2. However, the iterative implementation of these problems is often more efficient than recursive implementation , Although the code is slightly less readable .

3. When a problem is quite complex , When it is difficult to implement iteratively , At this point, the simplicity of recursive implementation can compensate for the runtime opening caused by it pin .

---

The end .