Function recursion and solving interesting problems

Catalog

Function recursion

Print in normal numerical order

Recursive numeric sequential printing

Fibonacci series question

The hanotta problem

---

Function recursion

The behavior of the function call itself is recursion . Can be called directly or indirectly , The essence is to turn a complex problem into a similar , Smaller problems . That is what we often call making big things small , It's trivial , It's an idea of dividing and ruling problems . One of the most important values of recursion is that it can reduce the amount of code , It can really improve the efficiency of development , But its disadvantages are also obvious , Let's use examples to explain the advantages and disadvantages of function recursion .

Print in normal numerical order

Suppose we enter a number , Want to print each bit of it in order .

Such as input :123

Output :1 2 3

Let's do it iteratively , Our basic idea is to input the number 123%10 Get a number in bits , Print , And then a/10 The value is assigned to a.

The code is as follows

#include<stdio.h>

void print()
{
	int  a = 0;
	int  i = 0;
	scanf("%d", &a);
	do 
	{
		printf("%d ", a % 10);
		a = a / 10;
	} while (a !=0);

}


int  main()
{
	print();
	return  0;
}

Input ：1234

But the output is ：4 3 2 1

This is obviously not what we want ！

Next, let's modify the function

void print()
{
	int  a = 0;
	int  i = 0;
	int  arr[10] = { 0 };
	int  count = 0;
	scanf("%d", &a);
	do 
	{
		arr[count]=a % 10;
		a = a / 10;
		count++;
	} while (a !=0);
	for (i = 0;i < count;i++)
	{
		printf("%d ", arr[count-1-i]);
	}

}


int  main()
{
	print();
	return  0;
}

Input ：1234

Output ：1 2 3 4

Results in line with expectations , But we used two cycles , Created a new array , This greatly increases the amount of code , And the logic becomes complicated .

Recursive numeric sequential printing

Is there a better solution , Next, we will introduce the method of array .

The main idea is to split the problem , We're not going to print with functions 1234 Do you ？ in other words :

print(1234)  The output is zero 1 2 3 4  Let's split it up

Split into print（123） and 4

Remodel print（12） and 3 4

print（1） and 2 3 4

We can adjust the function and printf To set the order of printing .

The procedure is as follows

void print(int x)
{
	if (x <= 9)
		printf("%d ", x);
	else
	{
		print(x / 10);
		printf("%d ", x % 10);
	}
}

int  main()
{
	int  a = 0;
	scanf("%d", &a);
	print(a);
	return  0;
}

Diagram of recursive process

 

Very compact code , It can be seen that for function recursion, we must have a restriction to limit the number of recursions , And every time you call recursion, you have to be closer to the constraints . In code x<=9 Is the limitation of recursion , When calling a recursive function x/10 Bring closer to the constraints .

Fibonacci series question

1 1 2 3 5 8 13 21 34 ...

This sequence starts at number one 3 A start , Each of these terms is equal to the sum of the first two terms . Fibonacci sequence can help us better understand the defects of recursion .

Each term is equal to the sum of the first two terms , in other words Fibonacci（n）=Fibonacci（n-1）+Fibonacci（n-2）.

int fibonacci(int n)
{
	if (n <= 2)
		return 1;
	else
		return fibonacci(n-1)+fibonacci(n-2);
}

int  main()
{
	int  n = 0;
	scanf("%d", &n);
	printf("%d ", fibonacci(n));
	return  0;
}

The code is as shown in the figure , But when n Reach a larger value , for instance 50 when , Stack overflow . Why is that ？

From the code, we can see that every time we enter a function, we recurse twice , At this time, the number of calls to the function increases by a geometric multiple , Almost want to use 2^n Secondary function , It's terrible .
Use iteration at this time , The calculation speed is obviously improved .

int fibonacci(int n)
{
	int  i = 0;
	int  a = 1;
	int  b = 1;
	int  c = 1;
		for (i = 0;i < n - 2;i++)
		{
			a = b;
			b = c;
			c = a + b;
		}
		return c;
}
int  main()
{
	int  n = 0;
	scanf("%d", &n);
	printf("%d ", fibonacci(n));
	return  0;
}

Be careful when using recursion .

The hanotta problem

It's said that in the ancient temple of India , There is one called the Hanoi Tower (Hanoi) The game of . The game is on a copper device , There are three rods ( Number A、B、C), stay A From the bottom up 、 Place in order from large to small 64 A gold plate . The goal of the game ： hold A All the gold plates on the pole are moved to C On the pole , And still keep the original order . Operating rules ： Only one plate can be moved at a time , And keep the big plate down all the time during the moving process , Small in , The plate can be placed during the operation A、B、C On any pole .

  Because the rule is that the market must be under , We are going to put A All the trays on the are transported to C, What must be done is to A The bottom disk is reserved , Transport the above inventory to B, Then move the largest plate to C.

hold A All the trays except the lowest ones are transported to B disc , Is it very similar to the original question , It's just that the largest tray is less transported , Then we can split the problem .

For example, we have to carry 7 A plate , Want to know the minimum handling times . Moving seven times is equal to moving two six times plus one .

hanoi(n）=2*hanoi(n-1)+1;

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

This is the end of knowledge sharing , Like my little friend , Like it 、 Comment on 、 Pay more attention to , I'll try to update it .