Catalog

#1 Function recursion

#2 Several simple examples of function recursion

#3 From the calculation of Fibonacci sequence, we can see the operational efficiency of recursive algorithm

 #4 Iteration and recursion

#5 The hanotta problem

#1 Function recursion

Function recursion refers to the function calling its own technology . Function recursion is very elegant in the way of thinking , It embodies the idea of transforming large-scale problems into similar problems of lower scale ; But in terms of algorithm efficiency , Recursion is a less efficient algorithm .

Recursive algorithm must meet two conditions ：1. There is an exit （ The solution to a minimum scale problem ）;2. The method of transforming large-scale problems into similar problems of lower scale . Use sequence The expression of is ：1. Know the initial items (a0,a1,a2 etc. );2. Know the recurrence formula (an+1=f(an)).        This ensures that recursion does not proceed indefinitely , It also reflects the function structure using recursive algorithm , It embodies the thinking mode of recursive algorithm （ Reduce the scale of the problem & Provide a solution to the lowest scale problem ）.

#2 Several simple examples of function recursion

// Print a given number from high to low num Every one of them 
void print(int num) {
	if (num <= 9 and num >= 0)// Equivalent to the beginning a0, For recursive exits 
		printf("%d	",num);
	else {
		print(num / 10);
		printf("%d	", num % 10);// Equivalent to the general term formula an=f(an-1)
	}

	return;
}
// Print 1234
//= Print 123+ Print 4
//= Print 12+ Print 3+ Print 4
//= Print 1+ Print 2+ Print 3+ Print 4
// Print 1 Is the lowest scale problem （ Print one digit ）, Both sides of the equal sign reflect the reduction of the scale of the problem 

// Do not use temporary variables , To calculate the length of a given string 
int my_strlen(char* str) {
	if (*str == '\0')
		return 0;        // Initial item , The lowest scale problem 
	else {
		return my_strlen(str+1)+1;// The recursive formula 
	}
}
// Calculation "China" The length of （ Pointer C）
//= Calculation hina The length of （ Move the pointer to the right h）+1
//= Calculation ina The length of （ Move the pointer to the right i）+1+1
//...
//= Calculation '\0' The length of （ Pointer '\0'）+1+1+1+1+1
// Calculation '\0' The length of the problem is the lowest scale 

// Calculate the... Of the Fibonacci sequence n term 1 1 2 3 5 8 13...
int sequence(int n) {

	if (n == 1 or n == 2) return 1;
	else
		return sequence(n - 1) + sequence(n - 2);
}

// The initial term and recurrence formula of the sequence are very obvious 

#3 From the calculation of Fibonacci sequence, we can see the operational efficiency of recursive algorithm

Calculation a(50) Need to compute a(49) and a(48), And calculation a(49) And calculate a(48) and a(47).a(48) Repeated calculations . Again , Calculation a(48) when ,a(47) It is calculated repeatedly . Pictured ：

a(50)
a(49)+a(48)
a(48)+a(47)+a(47)+a(46)
a(47)+a(46)+a(46)+a(45)+a(46)+a(45)+a(45)+a(44)
...
 It seems that the first few items will be calculated many times .
 We might as well calculate the following calculation a(40) when a(3) The number of times to be counted , This is due to the calculation a(50) It often takes 10min about , And calculation a(40) You may only need 10s about . From here, we can also see the time complexity difference of recursive algorithm . Let alone its spatial complexity （ A common problem with recursive algorithms is stack overflow ）.

int count3_40 = 0;// Use the recursive algorithm of Fibonacci sequence to find sequence(40) when sequence(3) The number of calculations 
int count30_40 = 0;// Use the recursive algorithm of Fibonacci sequence to find sequence(40) when sequence(30) The number of calculations 
int sequence(int n) {
	if (n == 3) ++ count3_40;
	if (n == 30) ++count30_40;
	if (n == 1 or n == 2) return 1;
	else
		return sequence(n - 1) + sequence(n - 2);

You can find a(3) It has been calculated more than 30 million times . It can be seen that the redundancy of recursive algorithm is high .

 #4 Iteration and recursion

The recursive algorithm for calculating Fibonacci sequence is changed into iteration , It's a cycle .

int sequence_loop(int n) {
	int a = 1;    //i
	int b = 1;	  //i+1
	int c = 0;	  //i+2
	if (n <= 2) return 1;
	for (int i = 3; i <= n;++i) {
		c = a + b;
		a = b;
		b = c;
		

	}
	return c;
	
}
// First consider the actual application scenario , Then consider how to realize . be called TDD, Test-driven development .
// Recursion involves a lot of repetition , Low efficiency . It should be replaced by iteration （ loop ）.

Recursive algorithm is elegant in its way of thinking , But the efficiency is not satisfactory . I want the simplicity of recursive algorithm , Want the efficiency of iterative algorithm , You should find The general method of changing recursive algorithm into iterative algorithm . I have encountered this method when learning data structures .

#5 The hanotta problem

The picture is taken from  https://www.biancheng.net/algorithm/tower_of_hanoi.html

The tower of Hanoi requires us to use the middle pillar , Put the leftmost n A disc from large to small moves to the far right , And meet the above two conditions .

According to the idea of recursive algorithm , We try to reduce n The scale of the first-order Hanoi Tower problem . We can actually ignore the biggest plate , And make another n-1 The plates are on three pillars from left to right （ Named as x,y,z） Move freely according to the rules .

So will x On n Move a plate to z On —— We remember that Hanoi(x,z,n)—— Can be converted to Hanoi(x,y,n-1)+Hanoi(x,z,1)+Hanoi(y,z,n-1). In this way, the scale of the problem is reduced .

that , Is there a solution to the simplest form of the tower of Hanoi problem ？ Obvious , There is . That is to say ：Hanoi(x,z,1).

therefore

Hanoi(x,z,1)

Hanoi(x,z,2)=Hanoi(x,y,1)+Hanoi(x,z,1)+Hanoi(y,z,1)

Hanoi(x,z,3)=Hanoi(x,y,2)+Hanoi(x,z,1)+Hanoi(y,z,2)

......

Hanoi(x,y,n-1)+Hanoi(x,z,1)+Hanoi(y,z,n-1)

So how to simulate columns and plates on a computer ？ You can use arrays （ The larger the subscript, the larger the number of elements that meet the characteristics of the stack ） And numbers from big to small （1,2,3,......,n-1,n）. For the convenience of some operations , You need to use a structure （ Contains other properties of arrays and columns ） To represent the column .

#define MAX 20
#include <stdio.h>
struct HanoiTower {
	int num = 0;// The number of plates in Hanoi Tower 
	int arr[MAX] = { 0 };// With the characteristics of stack , The element is put in the position with large subscript in the array first 
};
void generateHanoi(HanoiTower*, int);
void Hanoi(HanoiTower*, HanoiTower*,HanoiTower*, int);
int count = 0;// Used to record the times of Hanoi Tower , by 2^x-1

int main() {
	HanoiTower x;
	HanoiTower y;
	HanoiTower z;
	generateHanoi(&x,7);
	Hanoi(&x,&z,&y,7);


		return 0;
}

// Tower of Hanoi problem generator , For initialization HanoiTower Variable of type 
void generateHanoi(HanoiTower* m, int scale) {
	//scale Is the scale of the problem 
	m->num = scale;
	for (int i = MAX - 1; scale > 0 ; --i) {
		m->arr[i] = scale;
		scale--;
	}
	return;
}
// Hanoi Tower problem solver , Use recursive algorithm to solve the tower of Hanoi problem 
//source Source column ;dest Target column ;by Passing column 
void Hanoi(HanoiTower* source, HanoiTower* dest,HanoiTower* by, int scale) {
	if (scale == 1) {
		dest->arr[MAX - 1 - (dest->num)] = source->arr[MAX - (source->num)];
		source->arr[MAX - (source->num)] = 0;
		(source->num)--;
		(dest->num)++;
		++count;
	}
	else {
		Hanoi(source,by,dest,scale-1);
		Hanoi(source,dest,by,1);
		Hanoi(by,dest,source,scale-1);
	}

	return;
}