Recursion and recursion
To Iterate is Human,to Recures,Divine
Man understands iteration, God understands recursion
Ladder problem
Recursive Method
Space complexity: O(1)
Time complexity: O(2^n)
analysis:
- Space complexity: because recursion does not apply for additional space, it is O(1)
- Time complexity: the number of recursions increases in the form of a binary tree. It is easy to know that the time complexity of the code is related to the number of nodes of the binary tree, and O(2^n) is obtained
recursive method
Space complexity: O(1)
Time complexity: O(n)
analysis:
- Space complexity: because recursion does not apply for additional space, it is O(1)
- Time complexity: only one for loop can get the result, so it is O(n)
Case code: ladder java
public class Ladder {
//Recursive Method
public static int Recursion(int n){
//Termination conditions
if(n==1||n==2){
return n;
}
//Non terminating condition: returns the methods of the previous step and the previous two steps
return Recursion(n-1)+Recursion(n-2);
}
//recursive method
public static int Recurrence(int n){
if(n==1)return 1;
if(n==2)return 2;
int Part1 = 1;
int Part2 = 2;
int temp;//Create temporary variable
int sum = 0;//Create receive result variable as 0
for (int i = 3; i <= n; i++) {//tip: start with 3
sum = Part1+Part2;//sum needs to be equal to the first two
temp = Part2;
Part2 = sum;
Part1 = temp;
}
return sum;
}
public static void main(String[] args) {
System.out.println(Recurrence(4));//Recurrence
System.out.println(Recursion(4));//recursion
}
}
Factorial algorithm
Recursive Method
Space complexity: O(1)
Time complexity: O(n)
analysis:
- Space complexity: because recursion does not apply for additional space, O(1) is obtained
- Time complexity: the number of recursions is related to N, and the time is directly proportional to N, so O(n) is obtained
recursive method
Space complexity: O(1)
Time complexity: O(n)
analysis:
-
Space complexity: O(1) because there is no more space
-
Time complexity: recursion is easy to see that the number of code executions is related to N, and O(n) can be obtained
Case code: factorial java
public class Factorial {
//Recursive Method
public static int Recursion(int n) {
//Termination conditions
if (n == 1) return 1;
//The non terminating condition returns the multiplication degree of the previous number * n
return Recursion(n - 1) * n;
}
//recursive method
public static int Recurrence(int n) {
int sum = 1;//Let sum be equal to 1
for (int i = 1; i <= n; i++) {
sum *= i;//Multiply by n each time
}
return sum;//Finally, sum is returned
}
public static void main(String[] args) {
System.out.println(Recurrence(10));//Recurrence
System.out.println(Recursion(10));//recursion
}
}
fibonacci sequence
Recursive Method
Space complexity: O(1)
Time complexity: O(2^n)
analysis:
- Space complexity: because recursion does not apply for additional space, it is O(1)
- Time complexity: the number of recursions increases in the form of a binary tree. It is easy to know that the time complexity of the code is related to the number of nodes of the binary tree, and O(2^n) is obtained
recursive method
Space complexity: O(1)
Time complexity: O(n)
analysis:
- Space complexity: because the recursion does not apply for additional space, it is O(1)
- Time complexity: only one for loop can get the result, so it is O(n)
Case code: Fibonacci java
public class Fibonacci {
//Recursive Method
public static int Recursion(int n){
//Termination conditions
if(n==1||n==2){
return n;
}
//Non terminating condition: returns the methods of the previous step and the previous two steps
return Recursion(n-1)+Recursion(n-2);
}
//recursive method
public static int Recurrence(int n){
if(n==1)return 1;
if(n==2)return 2;
int Part1 = 1;
int Part2 = 2;
int temp;//Create temporary variable
int sum = 0;//Create receive result variable as 0
for (int i = 3; i <= n; i++) {//tip: start with 3
sum = Part1+Part2;//sum needs to be equal to the first two
temp = Part2;
Part2 = sum;
Part1 = temp;
}
return sum;
}
public static void main(String[] args) {
System.out.println(Recurrence(4));//Recurrence
System.out.println(Recursion(4));//recursion
}
}
Palindrome string
Recursive Method
Space complexity: O(1)
Time complexity: O(2^n)
analysis:
- Space complexity: because recursion does not apply for additional space, it is O(1)
- Time complexity: the number of recursions increases in the form of a binary tree. It is easy to know that the time complexity of the code is related to the number of nodes of the binary tree, and O(2^n) is obtained
recursive method
Space complexity: O(1)
Time complexity: O(n)
analysis:
- Space complexity: because the recursion does not apply for additional space, it is O(1)
- Time complexity: only one while loop can get time T(n)=n/2, so O(n)
Case code: palindrome java
public class Palindrome {
//Recursive method
public static boolean IsPalindereme01(String s) {
//Method of using pointer
int begin = 0;//Point to first subscript
int end = s.length() - 1;//Points to the last subscript
while (begin < end) {
if (s.charAt(begin) != s.charAt(end))
return false;//If there is inequality, return false
begin++;//Pointer plus one
end--;//Pointer minus one
}
//The end of the loop indicates that it is correct and returns true
return true;
}
//Recursive method
public static boolean IsPalindereme02(String s,int left,int right) {
//Termination conditions
if (right-left <= 1)//When the right pointer points to the right of the left pointer or is equal, it can be replaced by right < = left + 1
return true;
if (s.charAt(left) != s.charAt(right))//The charAt(a) function takes the character with the subscript a of the string
return false;//Returns false when inequality occurs
//Non termination conditions
else
return IsPalindereme02(s,left+1,right-1);//Continue the cycle
}
//test result
public static void main(String[] args) {
String s = "asdfghjklkjhgfdsa";
System.out.println(IsPalindereme01(s));
System.out.println(IsPalindereme02(s,0,s.length()-1));
s = "123";
System.out.println(IsPalindereme01(s));
System.out.println(IsPalindereme02(s,0,s.length()-1));
}
}
Hanoi
Recursive Method
Space complexity: O(1)
Time complexity: O(2^n)
analysis:
-
Space complexity: because recursion does not apply for additional space, it is O(1)
-
Time complexity:
-
T(n)=2(n-1)*2T(1)+1*(1+2+22+......+2^(n-1))
=2n+2n-1
=2^(n+1)-1
-
The time complexity of the recursive algorithm is O(2^n)
-
recursive method
If recursion is used, directly use the formula: H(n) = 2^n - 1
Case code: hannoidemo java
import java.util.Scanner;
public class hannoiDemo {
/**
* How many steps have you taken
*/
static int times;
//Recursive function
public static void hannoi(int n, char A, char B, char C) {
if (n == 1) {
move(n, A, C);
} else {
//Move the previous level to step B
hannoi(n - 1, A, C, B);
//Move the largest plate to tower C
move(n, A, C);
//Then move the plate on B to C
hannoi(n - 1, B, A, C);
}
}
//The time complexity of the recursive algorithm is O(2^n);
//Print move
public static void move(int disk, char M, char N) {
System.out.println("The first" + (++times) + "Secondary movement, plate" + disk + " " + M + "------->" + N);
}
public static void main(String[] args) {
char A = 'A';
char B = 'B';
char C = 'C';
System.out.println("The Hanoi tower game begins");
System.out.println("Please enter the number of plates:");
Scanner s = new Scanner(System.in);
int n = s.nextInt();
//Call Hanoi Tower
hannoi(n, A, B, C);
s.close();
}
}
additive decomposition
Recursive Method
Space complexity: O(1)
Time complexity: O(2^n)
analysis:
- Space complexity: because recursion does not apply for additional space, it is O(1)
- Time complexity: the number of recursions increases in the form of a binary tree. It is easy to know that the time complexity of the code is related to the number of nodes of the binary tree, and O(2^n) is obtained
Case code: test cpp
#include<iostream>
using namespace std;
int sum = 0;
/**
m=1,The positions of the exchange addends are treated as different decomposition schemes
When called, count = 0
*/
void dfs1(int n, int count, int* p)
{
if (n == 0) { //Recursive basis, output the result when reaching the leaf node
cout << sum << "=";
for (int i = 0; i < count; i++)
if (i == count - 1)
cout << p[i] << endl;
else
cout << p[i] << "+";
return;
}
for (int i = 1; i <= n; i++) {
p[count] = i;
dfs1(n - i, count + 1, p);
}
return;
}
/*
m=2,The position of the commutative addend is treated as the same decomposition scheme
When called, count = 0
*/
void dfs2(int n, int count, int* p)
{
if (n == 0) { //Recursive basis, output the result when reaching the leaf node
cout << sum << "=";
for (int i = 0; i < count; i++)
if (i == count - 1)
cout << p[i] << endl;
else
cout << p[i] << "+";
return;
}
int k = count > 0 ? p[count - 1] : 1; //The numbers in the array should be in non decreasing order
for (int i = k; i <= n; i++) {
p[count] = i;
dfs2(n - i, count + 1, p);
}
}
int main()
{
int n, m;
cin >> n >> m;
sum = n;
int* p = new int[n];
if (m == 1)
dfs1(n, 0, p);
else if (m == 2)
dfs2(n, 0, p);
return 0;
}