[function recursion] do you know all five classic examples of simple recursion?

🧸🧸🧸 Hello, guys , I'm pig skin brother 🧸🧸🧸

Today I want to talk about simple recursion 🥳🥳🥳

What is recursion

Definition of recursion ：
Recursion is an effective way to solve problems , In the process of recursion , The function calls itself as a subroutine .
That is to say, the programming skill of program call itself is called recursion . The idea of recursion is to transform a large and complex problem into a smaller problem than the original problem , After the problem is broken down into sub problems , The recursive call continues , Until the subproblem can be solved without further recursion .

The important idea of recursion is to enlarge and reduce

The most important thing about recursion is We need to avoid the occurrence of dead cycles and Correctness of logical relationship

Classic examples of recursion

1. Recursive simulation of library functions strlen

The code is as follows ：

int my_strlen(char* str)
{
    
	if (*str == '\0')
		return 0;
	else
	{
    
		return 1 + my_strlen(++str);
	}
}

int main()
{
    
	char str[] = "abcdef";
	printf("%d",my_strlen(str));

	return 0;
}

What we need to pay attention to is the cut-off condition of recursion

2. Recursive simulation realizes the inverse of string

The code is as follows ：

#include <string.h>
int my_strlen(const char* str)
{
    
	if (*str == 0)
	{
    
		return 0;
	}
	else
	{
    
		return 1 + my_strlen(++str);
	}
}
void reverse_string(char*str)
{
    
	int len = my_strlen(str);
	char* temp = *str;
	*str = *(str + len - 1);
	*(str + len - 1) = 0;
	if (my_strlen(str + 1) >= 2)
		reverse_string(str+1);
	*(str + len - 1) = temp;
	// Characters that need to be replaced to the second half , Each recursion creates a temp Save up ,
	// It is assigned to the second half only when the recursion ends and the backtracking begins , Because first of all, we have to deal with the second half 
	// Part of a set '\0'
}

int main()
{
    
	char str[] = "abcdef";
	reverse_string(str);
	puts(str);
	return 0;
}

3. Recursive and non recursive representations of Fibonacci sequences

The code is as follows ：

}
int fib(int n)
{
    
	 recursive 
	if (n == 1 || n == 2)
	{
    
		return 1;
	}
	else
	{
    
		return fib(n - 1) + fib(n - 2);
	}
	
	// Because Fibonacci is too inefficient if it uses recursion , So use non recursive 
	// Non recursive 
	int a = 1, b = 1, c = 1;
	while (n > 2)
	{
    
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}


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

4. Recursive frog jumping steps

The code is as follows ：

// Frogs jump the steps 
int JumpFloor(int n)
{
    
	if (n == 1)
		return 1;
	else if (n == 2)
		return 2;
	else
	{
    
		return JumpFloor(n - 1) + JumpFloor(n - 2);
	}
}
int main()
{
    	
	int n;
	scanf("%d",&n);
	printf("%d",JumpFloor(n));
	return 0;
}

5. Recursive Hanoi Tower problem

The code is as follows ：

void move(pos1, pos2)
{
    
	printf("%c--->%c\n",pos1,pos2);
}

void hanio(int n,char pos1,char pos2,char pos3)
{
    
	if (n == 1)
	{
    
		printf("%c--->%c\n",pos1,pos3);

	}
	else
	{
    
		hanio(n - 1, pos1, pos3, pos2);
		move(pos1, pos3);
		hanio(n - 1, pos2, pos1, pos3);
	}
	
}

int main()
{
    
	int n;
	scanf("%d",&n);
	char pos1 = 'A', pos2 = 'B', pos3 = 'C';
	hanio(n,pos1,pos2,pos3);

	return 0;
}

---

habla mi corazon

Today's sharing is here , It will be updated continuously in the future ！！ Thank you for your support