C language: deep learning recursion

The authors introduce ： Hello everyone , I'm the king of fishing, chubby , You can call me Xiao Du
Author URI ： Fishing king chubby personal blog homepage .
The author's gitee: Little bit _ Dudu's individual gitee
Series column ： 【 from 0 To 1, roaming c The world of language 】
Xiao Du studies with everyone , Progress together ！ Do what you can , Write every blog , Revel in the joy of your progress 🤭. If there are mistakes in the article , Welcome to the comments section ️ correct . Let's start today's study ！

Preface

This article is for the study of recursion , I hope you can deepen your understanding of recursion through these questions ！
notes ： This article only discusses the problem from the recursive method , There are many ways , You can find and learn by yourself ！

application 1： Monkeys eat peaches

The problem of monkeys eating peaches ： There is a pile of peaches , The monkey ate half of it on the first day , And one more ！ Later, every day monkeys eat half of them , And then one more . When it comes to the third 10 days , When you want to eat again （ I haven't eaten yet ）, Only found 1 A peach .
ask ： How many peaches are there in the first place ？

#include<stdio.h>

/*  The problem of monkeys eating peaches ： There is a pile of peaches , The monkey ate half of it on the first day ,  And one more ！ Later, every day monkeys eat half of them , Then more   Eat one . When it comes to the third 10 days , When you want to eat again （ I haven't eaten yet ）, Only found 1  A peach . ask ： How many peaches are there in the first place ？  Thought analysis （ Backstepping ） 1.day = 10  when   Yes  1 A peach  2.day = 9  when   Yes  (day10 + 1)* 2 = 4 3.dat = 8  when   Yes  (day9 + 1) * 2 = 10 4. Law is   The peach of the previous day  = （ Peaches the next day  + 1）* 2 5. recursive  */

int peach(int day)
{
    
	if (day == 10)
	{
    
		return 1;// The first 10 It's just 1 A peach 
	}
	else if (day >= 1 && day <= 9)
	{
    
		return (peach(day + 1) + 1) * 2;
	}
	else
	{
    
		printf("day stay 1-10 Between ");
		return -1;
	}

}

int main()
{
    
	int day = 0;
	scanf("%d", &day);
	int ret = peach(day);
	printf(" The first %d There are altogether ：%d individual \n",day, ret);
	return 0;
}

Effect display ：

application 2： Fibonacci problem

Fibonacci sequence （Fibonacci sequence）, Also called golden section series 、 Because mathematician Leonardo · Fibonacci （Leonardoda Fibonacci） Take rabbit breeding as an example , It is also called “ Rabbit Series ”, It refers to such a sequence ：1、1、2、3、5、8、13、21、34、…… In Mathematics , The Fibonacci sequence is defined recursively as follows ：F(1)=1,F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3,n ∈ N*）

The Fibonacci sequence refers to a sequence that looks like this ：
1,1,2,3,5,8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765,
10946, 17711, 28657, 46368 ……
This sequence starts at number one 3 A start , Each of these terms is equal to the sum of the first two terms .

The recursive method ：

#include<stdio.h>

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

Effect display ：

️ Have you noticed that , Just ask for the first 8 Fibonacci requires so many processes , If o 55 Fibonacci number is even greater , It will take a long time ？ Even the computer will take a lot of time to help you calculate , Therefore, it is not recommended to use recursive method to solve Fibonacci sequence , So what else can we do ？

Non recursive solution ：

️ We find that using recursion is from the back to the front , Then can we try to calculate from the past to the future ？

#include<stdio.h>

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

Effect display ：

application 3： The hanotta problem

The legend of Hanoi Tower
Hanoi ： Hanoi （ Also known as the river tower ） The problem is a puzzle toy from an ancient Indian legend . Vatican made three diamond pillars when he created the world , Stack on a column from bottom to top in order of size 64 A disc . Brahma ordered Brahman to rearrange the disc on another pillar in order of size from below . And stipulate , You can't enlarge a disc on a small disc , Only one disc can be moved between the three pillars at a time .
If you move every second , How long will it take ？ It takes... To move these gold pieces 5845.54 More than one hundred million , The life expectancy of the solar system is said to be tens of billions of years . Really passed 5845.54 In one hundred million, , All life on earth , Together with the Vatican tower 、 Temples, etc , It's long gone .
So how do we solve it ？
My solution is to put A Hold up the column and move it C On the pillars ！
poof ！ To make fun of ~~
️ After we know the background , Let me explain the process of Hanoi Tower step by step ！

This is the original plate ：

Now our task is to say through a method A All the discs on the disc move to C On the plate , And it is required that only one disc can be moved at a time, and the small disc cannot be placed under the large disc .

---

n It means how many discs there are
When n=1 when ： Move 1 Direction A—>C; Move once

When n=2 when ： Move 1 Direction A—>B;
Move 2 Direction A—>C;
Move 1 Direction B—>C; Move three times

When n=3 when ： Move 1 Direction A—>C;
Move 2 Direction A—>B;
Move 1 Direction C—>B;
Move 3 Direction A—>C;
Move 1 Direction B—>A;
Move 2 Direction B—>C;
Move 1 Direction A—>C; Move seven times

---

Use exhaustive methods , Calculate the number of movements of Hanoi Tower ：

1-4 The moving steps of step Hanoi Tower ：

---

We can find that the disc moves regularly :

1> hold n-1 A disc consists of A Move to B;
2> The first n A disc consists of A Move to C;
3> hold n-1 A disc consists of B Move to C;
We are n-1 A disk is analyzed as a whole ,

How to n-1 A disk from A Move to B Well ？（ With the help of C The tower moved to B On ）

We can n-2 A disk is analyzed as a whole ：
1> hold n-2 A disc consists of A Move to C;
2> The first n-1 A disc consists of A Move to B;
3> hold n-2 A disc consists of C Move to B;

How to n-1 A disk from B Move to C Well ？（ With the help of A The tower moved to C On ）

1> hold n-2 A disc consists of B Move to A;
2> The first n-1 A disc consists of B Move to C;
3> hold n-2 A disc consists of A Move to C;

a key ：
（1） The middle step is to turn the largest plate from A Move to C Up ;
（2） The middle step can be regarded as A On n-1 A plate by means of C The tower moved to B On ,
（3） The middle step can be seen as B On n-1 A plate by means of A The tower moved to C On

It is not difficult for us to deduce recursive expressions ：f(n-1) + 1 + f(n-1) = 2 * f(n - 1) + 1

Then you can implement the following code ：

#include<stdio.h>

int step_number(int num)
{
    
	if (1 == num)
	{
    
		return 1;
	}
	else
	{
    
		return 2 * step_number(num - 1) + 1;
	}
}

void move(int num,char a,char b,char c)
{
    
	//num  Indicates the number of moves 
	//a,b,c respectively A tower ,B tower ,C tower 
	if (1 == num)
	{
    
		printf("%c->%c\n",a,c);
	}
	else
	{
    
		// If there are multiple disks , It can be seen as two disks , All the disks at the bottom and top 
		//1. Move all the disks above to b, With the help of c
		move(num - 1, a, c, b);
		//2. Put the bottom plate , Move to c
		printf("%c->%c\n",a,c);
		//3. And then b All the trays of the tower , Move to c, With the help of a
		move(num - 1, b, a, c);
	}
}

int main()
{
    
	int num = 0;
	scanf("%d", &num);// Number of towers 
	move(num,'A', 'B', 'C');
	int ret = step_number(num);
	printf(" complete %d The Hanoi Tower on the first floor needs %d Step \n", num, ret);
	return 0;
}

Effect display ：

summary

The application of recursive knowledge learning also includes eight queens 、 Mouse maze walking and other applications , These are very difficult for today's Xiaodu , Wait for Xiaodu to master it completely , It will be updated ！ I hope you can support me a lot ！