Table of Contents
1. What is a function?
2. Classification of functions in C language
2.1 Library functions:
strcpy
memset
2.2 Custom functions
3. Function parameters
3.1 Actual parameters (actual parameters)
3.2 Formal parameters (formal parameters)
4. Function call
4.1 Call by value
4.2 Call by address
5. Nested calls and chained access of functions
5.1 Nested calls
5.2 Chain access
6. Function declaration and definition
6.1 Function declaration:
6.2 Function definition
7. Function recursion
7.1 What is recursion
7.2 Two necessary conditions for recursion
7.2.1 Exercise 1
7.2.2 Exercise 2
7.3 Recursion and iteration
7.3.1 Exercise 3
7.3.2 Exercise 4
1. What is the function
In mathematics we often see the concept of functions. But do you know the functions in C language?
Wikipedia definition of function: subroutine
- In computer science, a subroutine (English: Subroutine, procedure, function, routine, method, subprogram, callable unit) is a part of the code in a large program, consisting of one or more statement blocks. It is responsible for completing a specific task and is relatively independent from other code.
- Generally, there will be input parameters and return values, providing encapsulation and hiding of details of the process. These codes are usually integrated into software libraries.
2. Classification of functions in C language
- Library Functions
- Custom function
2.1 library function:
Why are there library functions?
- We know that when we learn C language programming, we always want to know the result after writing a code, and want to print the result on our screen. At this time we will frequently use a function: printing information to the screen in a certain format (printf).
- In the process of programming, we will frequently do some string copy work (strcpy).
- In programming, we also calculate, and we always calculate operations such as n raised to the kth power (pow).
Like the basic functions we described above, they are not business code. Every programmer may use it during our development process. In order to support portability and improve program efficiency, the basic library of C language provides a series of similar library functions to facilitate programmers to develop software.
So how to learn library functions?
Here we take a brief look: www.cplusplus.com
To briefly summarize, the commonly used library functions in C language include:
- IO function
- String manipulation functions
- Character manipulation functions
- Memory operation function
- time/date functions
- Math functions
- Other library functions
Let’s refer to the documentation and learn several library functions:
strcpy
char * strcpy ( char * destination, const char * source );
memset
void * memset ( void * ptr, int value, size_t num );
Note:
But one secret that library functions must know is: when using library functions, the header file corresponding to #include must be included.
Here we refer to the documentation to learn the above library functions in order to master the usage of the library functions.
2.2 Custom Function
If library functions can do everything, what do programmers need to do?
All the more important are custom functions.
Custom functions have the same function name, return value type and function parameters as library functions.
But the difference is that we design these ourselves. This gives programmers a lot of room to play.
Function composition:
ret_type fun_name(para1, * )
{
statement; //statement item
}
ret_type return type
fun_name function name
para1 function parameter
Example 1: Write a function that finds the maximum of two integers.
#include <stdio.h>
//Design of get_max function
int get_max(int x, int y)
{
return (x>y)?(x):(y);
}
int main()
{
int num1 = 10;
int num2 = 20;
int max = get_max(num1, num2);
printf("max = %d\
", max);
return 0;
}
Example 2: Write a function to exchange the contents of two integer variables.
#include <stdio.h>
//Implemented as a function, but cannot complete the task
void Swap1(int x, int y)
{
int tmp = 0;
tmp = x;
x = y;
y = tmp;
}
//Correct version
void Swap2(int *px, int *py)
{
int tmp = 0;
tmp = *px;
*px = *py;
*py = tmp;
}
int main()
{
int num1 = 1;
int num2 = 2;
Swap1(num1, num2);
printf("Swap1::num1 = %d num2 = %d\
", num1, num2);
Swap2( & amp;num1, & amp;num2);
printf("Swap2::num1 = %d num2 = %d\
", num1, num2);
return 0;
}
3. Parameters of function
3.1 Actual parameters (actual parameters)
The parameters that are actually passed to the function are called actual parameters. Actual parameters can be: constants, variables, expressions, functions, etc. No matter what type of quantities the actual parameters are, they must have definite values when making a function call so that these values can be passed to the formal parameters.
3.2 Formal parameters (formal parameters)
Formal parameters refer to the variables in parentheses after the function name. Because formal parameters are only instantiated (memory units allocated) when the function is called, they are called formal parameters. Formal parameters are automatically destroyed after the function call is completed. Therefore formal parameters are only valid within functions.
The parameters x, y, px, and py in the Swap1 and Swap2 functions in Example 2 above are all formal parameters. The num1 and num2 passed to Swap1 in the main function and the &num1 and &num2 passed to the Swap2 function are actual parameters.
Here we analyze the actual parameters and formal parameters of the function:
The memory allocation corresponding to the code is as follows:
Here you can see that when the Swap1 function is called, x and y have their own space and have the same content as the actual parameters. So we can simply think:After the formal parameter is instantiated, it is actually equivalent to a temporary copy of the actual parameter.
4. Function call
4.1 Call by value
The formal parameters and actual parameters of a function occupy different memory blocks respectively, and modifications to the formal parameters will not affect the actual parameters.
4.2 Call by address
- Calling by address is a way of calling a function by passing the memory address of the variable created outside the function to the function parameter.
- This method of passing parameters can establish a real connection between the function and the variables outside the function, that is, the variables outside the function can be directly manipulated inside the function.
5. Nested calls and chained access of functions
Functions can be combined according to actual needs, that is, they can call each other.
5.1 Nested Call
#include <stdio.h>
void new_line()
{
printf("hehe\
");
}
void three_line()
{
int i = 0;
for(i=0; i<3; i + + )
{
new_line();
}
}
int main()
{
three_line();
return 0;
}
Functions can be called nested, but not defined.
5.2 Chained Access
Use the return value of one function as a parameter of another function.
#include <stdio.h>
#include <string.h>
int main()
{
char arr[20] = "hello";
int ret = strlen(strcat(arr,"bit")); //Here we introduce the strlen function
printf("%d\
", ret);
return 0;
}
#include <stdio.h>
int main()
{
printf("%d", printf("%d", printf("%d", 43)));
//What is the result?
//Note: The return value of the printf function is the number of characters printed on the screen.
return 0;
}
6. Declaration and definition of function
6.1 Function declaration:
- Tell the compiler what the function is called, what the parameters are, and what the return type is. But whether it exists or not cannot be determined by the function declaration.
- The declaration of a function generally appears before the use of the function. It must be declared first and then used.
- Function declarations are generally placed in header files.
6.2 Function Definition
The definition of a function refers to the specific implementation of the function and explains the functional implementation of the function.
Contents of test.h
Place the declaration of the function
#ifndef __TEST_H__ #define __TEST_H__ //declaration of function int Add(int x, int y); #endif //__TEST_H__
Contents of test.c
Implementation of placement function
#include "test.h"
//Implementation of function Add
int Add(int x, int y)
{
return x + y;
}
Seven. Function Recursion
7.1 What is recursion
The programming technique in which a program calls itself is called recursion.
Recursion as an algorithm is widely used in programming languages. A process or function has a method of directly or indirectly calling itself in its definition or description. It usually transforms a large and complex problem into a smaller-scale problem similar to the original problem to solve, using a recursive strategy. Only a small amount of programs are needed to describe the multiple repeated calculations required in the problem-solving process, which greatly reduces the amount of program code.
The main way of thinking about recursion is to make big things smaller
7.2 Two necessary conditions for recursion
- There is a constraint, and when this constraint is met, the recursion will no longer continue.
- Each recursive call gets closer and closer to this limit.
7.2.1 Exercise 1
Accepts an integer value (unsigned) and prints each bit of it in order. For example: input: 1234, output 1 2 3 4
#include <stdio.h>
void print(int n)
{
if(n>9)
{
print(n/10);
}
printf("%d ", n );
}
int main()
{
int num = 1234;
print(num);
return 0;
}
7.2.2 Exercise 2
Writing functions does not allow the creation of temporary variables to find the length of a string.
#incude <stdio.h>
int Strlen(const char*str)
{
if(*str == '\0')
return 0;
else
return 1 + Strlen(str + 1);
}
int main()
{
char *p = "abcdef";
int len = Strlen(p);
printf("%d\
", len);
return 0;
}
7.3 Recursion and Iteration
7.3.1 Exercise 3
Find the factorial of n. (overflow is not considered)
int factorial(int n)
{
if(n <= 1)
return 1;
else
return n * factorial(n-1);
}
7.3.2 Exercise 4
Find the nth Fibonacci number. (overflow is not considered)
int fib(int n)
{
if (n <= 2)
return 1;
else
return fib(n - 1) + fib(n - 2);
}
But we discovered something was wrong;
When using the fib function, it is particularly time-consuming if we want to calculate the 50th Fibonacci number. If you use the factorial function to find the factorial of 10000 (regardless of the correctness of the result), the program will crash.
why?
We found that many calculations are actually repeated during the calling process of the fib function. If we modify the code:
int count = 0;//Global variable
int fib(int n)
{
if(n==3)
count + + ;
if (n <= 2)
return 1;
else
return fib(n - 1) + fib(n - 2);
}
Finally, we output the count, which is a very large value.
So how do we improve?
- When debugging the factorial function, if your parameters are relatively large, an error message such as stack overflow will be reported.
- The stack space allocated to the program by the system is limited, but if an infinite loop or (dead recursion) occurs, this may cause the stack space to be continuously allocated, and eventually the stack space will be exhausted. This phenomenon is called stack overflow. .
So how to solve the above problems:
- Rewrite recursion into non-recursion.
- Use static objects instead of nonstatic local objects. In recursive function design, static objects can be used instead of nonstatic local objects (that is, stack objects). This not only reduces the overhead of generating and releasing nonstatic objects during each recursive call and return, but the static object can also save the intermediate state of the recursive call. , and can be accessed by each calling layer.
For example, the following code is implemented in a non-recursive way:
//Find the factorial of n
int factorial(int n)
{
int result = 1;
while (n > 1)
{
result *= n ;
n -= 1;
}
return result;
}
//Find the nth Fibonacci number
int fib(int n)
{
int result;
int pre_result;
int next_older_result;
result = pre_result = 1;
while (n > 2)
{
n -= 1;
next_older_result = pre_result;
pre_result = result;
result = pre_result + next_older_result;
}
return result;
}
hint:
- Many problems are explained in recursive form simply because it is clearer than non-recursive form.
- But iterative implementations of these problems tend to be more efficient than recursive implementations, although the code is slightly less readable.
- When a problem is too complex to be solved iteratively, the simplicity of the recursive implementation can compensate for the runtime overhead.