当前位置：网站首页>6. Function recursion

6. Function recursion

2022-07-06 13:26:00 【It's Wang Jiujiu】

Catalog

1. What is recursion ？

2. Necessary conditions for recursion

3. Explanation of specific examples

Example 1： establish my_strlen function , Simulation Implementation strlen function .

Example 2： Find the Fibonacci number

Example 3： Count the daffodils

4. Recursion and iteration

The difference between recursion and iteration

Find Fibonacci number by iteration

5. Recursive exercises

1. What is recursion ？

The programming skill of program calling itself is called recursion （ recursion）.
Recursion as an algorithm is widely used in programming languages . A procedure or function has a method that directly or indirectly calls itself in its definition or description , It usually transforms a large and complex problem into a smaller problem similar to the original problem to solve .
The recursion strategy only needs a few programs to describe the repeated calculation needed in the process of solving problems , Greatly reduces the amount of code in the program .

The main way to think about recursion is ： Turn the big thing into a small one

2. Necessary conditions for recursion

1、 Recursion must meet the constraints , When this condition is met , Recursion stops .

2、 After every recursion, we must approach the limiting condition .

The use of recursion must meet the above two conditions at the same time , When one of them is not satisfied , The function will fall into dead recursion .

3. Explanation of specific examples

Example 1： establish my_strlen function , Simulation Implementation strlen function .

Iterative method

The core idea ：

strlen Is used to find the length of the string , The result does not contain a terminator '\0'. for example ： use strlen Find string “abcdef” The length of is 6.（strlen The return value of is an unsigned integer , Here, the return type of the function we simulate is integer ）
because strlen The result of does not contain a terminator '\0', So we can take \0 As a condition of termination ： Read from the first character , If the location is not \0, Iteration continues , Until I read \0 when , Stop reading .

Common method （ establish 2 Temporary variables ）

#include<stdio.h>

int my_strlen(char ch[])//[] It's the same whether you write numbers or not 
{
	int count = 0;// Count 
	int i = 0;// After each iteration, the position is moved back by one character 
	while (ch[i] != '\0')
	{
		count++;
		i++;
	}
	return count;
}

int main()
{
	char ch[] = "abcdef";
	int num = my_strlen(ch);
	printf("%d\n", num);
	return 0;
}

Pointer method （ establish 1 Temporary variables ）

If you know something about pointer , You can also use pointers , It is more convenient .

#include<stdio.h>

int my_strlen(char* ch)
{
	int count = 0;
	while (*(ch++) != '\0')//*ch To dereference 
	{
		count++;
	}
	return count;
}

int main()
{
	char ch[] = "abcdef";
	int num = my_strlen(ch);
	printf("%d\n", num);
	return 0;
}

It can be achieved smoothly through iteration strlen The function of , But whether it's a common method or a method using pointers , We all created temporary variables count To count , Suppose you don't use temporary variables ？ And how to ？

Recursive method

The core idea ：

Recursively use functions to call themselves , In order to simplify some complex things .
Set up my_strlen Function simulation implementation , Suppose we find the string “abcedf” The length of , We can put the string “abcdef” Split into 1+ character string “bcdef”, Find string “abcedf” It becomes asking 1+"bcdef" The problem. , seek "bcdef" The length of can call our set my_strlen function .
And then “bcdef” Split into 1+ character string “cdef”...... Until the last character is left ‘f’ when , hold f Split into 1+‘\0’, When read to ‘\0’ when , Stop calling my_strlen function , Recursion ends .

Deliver ： Recursion begins with , We split the string until \0 This action is to pass .

return ： Only after recursion can we return , When the function reaches the limit , When the function can no longer be called , Take the result of this function as the return value , Return to the previous function , Until you return to the first call to the function .

Recursion and regression in recursion are corresponding , The times of delivery and return are the same , For example, a function recurses 6 Time , Then it must be implemented 6 Secondary delivery ,6 Secondary regression .

#include<stdio.h>

int my_strlen(char* ch)
{
	if (*ch != 0)
		return 1 + my_strlen(ch+1);
	else
		return 0;
}
int main()
{
	char ch[] = "abcdef";
	int num = my_strlen(ch);
	printf("%d\n", num);
	return 0;
}

In the above code ,ch Is the first address element of the string ,*ch To be right ch Dereference the stored address , Find the element in the string through this address .

Every time you recurse, the address is backward +1, Because with char* Received by the pointer type of ch The address of , So here +1 Expressed as one byte backward , If it is int* Pointer type of ,+1 It is backward every time 4 Bytes .（ Don't use it here ++ch, Will completely change ch）.

When read '\0' when , Stop recursion .

Example 2： Find the Fibonacci number

Fibonacci number ：1、1、2、3、5、8、13、21、34、56...... Start with the third item , The value of each term is equal to the sum of the first two terms .

The core idea ：

When n=5 when , The first 5 Fibonacci Numbers = The fourth Fibonacci number （n-1）+ The third Fibonacci number （n-2）
The fourth Fibonacci number = The third Fibonacci number （n-2）+ The second Fibonacci number （n-3）
The third Fibonacci number = The second Fibonacci number 1+ The first Fibonacci number 1

So let's find the fifth Fibonacci number , It turns into a quest n The second Fibonacci sum m The first question about Fibonacci number .

#include<stdio.h>
 
int fibo(int n)
{
	if (n > 2)
		return fibo(n - 1) + fibo(n - 2);
	else
		return 1;
}
 
int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d\n", fibo(n));
	return 0;
}

Example 3： Count the daffodils

Count all daffodils , The Narcissus count is a three digit number , The sum of the cubes of each number is equal to itself .

for example ： $153=1^{3}+5^{3}+3^{3}$ , so 153 It's Narcissus .

The core idea ：

for example ： seek 125 Your cube

First ,125 It can be divided into 12 and 5, seek 5 The cube of + seek 12 Your cube
secondly ,12 It can be divided into 2 and 5, seek 2 The cube of + seek 1 Your cube
Last ,1 Just itself , seek 1 The cube of .

How to integrate 125 Split into 12 and 5 Well ？

There will be 125/10, Integer division quotient 12; take 125%10, Take the remainder 5.

#include<stdio.h>
#include<math.h>

int flo(int i)
{
	int sum = 0;
	if (i / 10 != 0)
	{
		sum = flo(i / 10);
	}
	return sum += pow((i % 10), 3);
}

int main()
{
	int i = 0;
	for (i = 100; i < 1000; i++)
	{
		if (flo(i) == i)
		{
			printf("%d It's Narcissus \n", i);
		}
	}
	return 0;
}

return sum += pow((i % 10), 3); It can be understood as ：

1、sum += pow((i % 10), 3);

2、return sum;

When 1/10=0 when , Expression is false , No longer call functions , Start with the next statement , Calculation sum Value , then return To the previous recursion , Until all return End , Recursion ends .

4. Recursion and iteration

The difference between recursion and iteration

In the above calculation of Fibonacci number , If you ask for the second 35 Fibonacci Numbers , The program will soon give the result ; But if you ask for the number 50 Fibonacci Numbers , The program will run very slowly .

This is because when calculating Fibonacci number , We turn all the questions into asking n The first Fibonacci number and the m Fibonacci Numbers .

Just find the fifth Fibonacci number , So I called 9 The sub function itself . If you ask for the number 40 A Fibonacci number ？ How many times will the function be called ？

Set a global variable here count, Count the number of calls to the function .

int count = 0;
#include<stdio.h>

int fibo(int n)
{
	count++;
	if (n > 2)
		return fibo(n - 1) + fibo(n - 2);
	else
		return 1;
}

Please 40 Fibonacci numbers call 2 More than 100 million functions , Every time you call a function, you need to open up a space in the stack , However, the space of stack area is limited , When the stack area is full , The program can't go on .

When this happens , It is often more efficient to use iteration , Or use static Object instead of local variable object , This frees up space in the stack .

Comparison between iteration and recursion
The way	advantage	shortcoming
recursive	The form is clear , Clear thinking	Slow running speed , Stack area is easy to overflow
iteration	More efficient , Faster	Poor code readability

Find Fibonacci number by iteration

The core idea ：

By creating temporary variables , Store the result of adding the first two items , And as the added project in the next iteration .
To prevent data overflow , Here we use unsigned long long To store our results .

#include<stdio.h>
unsigned long long fibo(int n)
{
	unsigned long long sum=0;
	unsigned long long St=0;
	unsigned long long Sec=0;
	sum = Sec = 1;
	while (n > 2)
	{
		n -=1;
		St = Sec;
		Sec = sum;
		sum = St + Sec;
	}
	return sum;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	printf(" The first %d The Fibonacci number is %llu\n",n,fibo(n));
	return 0;
}

The first 50 The Fibonacci number is 12586269025, nearly 126 Billion .

The first 100 The Fibonacci number is 3736710778780434371,373 Around Beijing ,unsigned long long The maximum value stored is 18446744073709551615, But is 1844 Around Beijing . However, such a large number is only iterative 98 The results obtained this time .

“ Short step , A thousand miles ; Don't product the little stream , Beyond into the sea . Steed leap , Not ten step ; Dobbin ten driving , Work in . Cheese, instead , Don't fold the deadwood ; perseverance , Stone can be used in .”C The same is true of language learning , Make progress every day , Today is a little more learned than yesterday , Tomorrow will learn one more point than today , I believe we can all achieve something in the end , The future is boundless .