Recursive algorithm
1. Overview of Recursive Algorithm
- Recursion/recursion can be understood as both an algorithmic idea and an algorithm implementation method.
- The divide-and-conquer algorithm strategy is mainly implemented through recursion, and large-scale problems are decomposed into small-scale problems; the dynamic programming algorithm is mainly implemented through recursion
- The core of recursion and recursion is actually recursion.
- Recursion: solving problems from top to bottom, from unknown to known
- Recursion: solving problems from bottom to top, from known to unknown
(1) Algorithm features:
The solution of a problem requires a series of calculations
There is always some kind of interrelationship between the known conditions and the problem being asked.
Find the quantitative relationship between the preceding and following processes (i.e., recursive formula), which is divided into forward and reverse inferences.
Whether pushing forward or backward, the key is to find the recurrence formula
(2)Key:
When using recursive algorithms to solve problems, the key is to find the recursive formula and boundary conditions (critical conditions)
(3) Push forward and backward
(4) Use recursion method to solve:
Fibonacci sequence, number of moves of the Tower of Hanoi, monkey eating peaches, digital triangle (succession method), dominoes filling the square, bee route, eating candy, insect reproduction, digit problem, dividing apples, stepping on the square, Climbing stairs (openjudge question)
2. Find the Fibonacci Sequence
The first 40 numbers of the (Fibonacci) sequence. This sequence has the following characteristics: the first and second numbers are 1 and 1. Starting from the 3rd number, this number is the sum of the two preceding numbers. Right now:
3.C language implementation
#include <stdio.h>
#include <stdlib.h>
int Fibonacci(n) //Rabbit litter algorithm
{
int t1,t2;
if(n==1||n==2)
{
return 1;
}
else
{
t1=Fibonacci(n-1);
t2=Fibonacci(n-2);
return t1 + t2;
}
}
void main()
{
int n,num;
printf("Recursive algorithm to solve rabbit litter problem!\\
");
printf("Please enter the time first:");
scanf("%d", & amp;n);
num=Fibonacci(n);
printf("After %d months, a total of %d pairs of rabbits can be reproduced!\\
",n,num);
}
4.C++ language implementation
#include<iostream>
using namespace std;
int main()
{
int f[101],n;
cin>>n;
f[1]=1;f[2]=1;
for(int i=3;i<=n;i + + )
f[i]=f[i-1] + f[i-2];
for(int i=0;i<n;i + + )
{
if(i%5==0)//5 numbers in one line
cout<<endl;
cout<<f[i]<<'\t';
}
cout<<endl;
return 0;
}
5.Java language implementation
package com.xxx.huali.hualitest.fibonacci;
public class Main {
\t
/***
* Recursive thinking
* Time complexity O(n*n)
* @param n
* @return
*/
public static long fib1(int n) {
if(n<1)
return -1;
if(n==1||n==2)
return 1;
return fib1(n-2) + fib1(n-1);
}
\t
/**
*Introduce an array and calculate the value of each item
* Time complexity O(n)
* Space complexity O(n)
* @param n
* @return
*/
public static long fib2(int n) {
if(n<1)
return -1;
long[] data = new long[n + 1];
data[1] = 1;
data[2] = 1;
for(int i=3;i<=n;i + + )
data[i] = data[i-1] + data[i-2];
return data[n];
}
\t
/***
* Dynamic programming ideas, iterative calculations
* Time complexity O(n)
* Space complexity O(1)
* @param n
* @return
*/
public static long fib3(int n) {
long i,a,b;
if(n<1)
return -1;
if(n==1||n==2)
return 1;
a = 1;
b = 1;
for(i=3;i<=n;i + + ) {
b = a + b;
a = b - a;
}
return b;
}
\t
/***
* Calculated based on derivation formula
* Characteristic equation x^2 = x + 1
* @param n
* @return
*/
public static long fib4(int n) {
double result = 0;
double sqrt5 = Math.sqrt(5);
result = (Math.pow((1 + sqrt5)/2, n)-Math.pow((1-sqrt5)/2,n))/sqrt5;
return (long)result;
}
\t
/***
* Matrix fast power algorithm
* Time complexity O(logn)
* @param n
* @return
*/
public static long fib5(int n) {
if(n<1)
return -1;
if(n==1||n==2)
return 1;
long[][] result = {<!-- -->{1},{0}};
long[][] tem = {<!-- -->{1,1},{1,0}};
while(n!=0) {
if((n &1)==1)
result = matrixMultiply(tem, result);
tem = matrixMultiply(tem, tem);
n>>=1;
}
return result[1][0];
}
\t
public static long[][] matrixMultiply(long[][] a,long[][] b){
int rows = a.length;
int cols = b[0].length;
long[][] matrix = new long[rows][cols];
\t\t
for(int i=0;i<rows;i + + ) {
for(int j=0;j<cols;j + + ) {
for(int k=0;k<a[i].length;k + + ) {
matrix[i][j] + = a[i][k] * b[k][j];
}
}
}
\t\t
return matrix;
}
\t
public static void main(String[] args) {
int n = 71;
//System.out.println(fib1(n));
System.out.println(fib2(n));
System.out.println(fib3(n));
System.out.println(fib4(n));
System.out.println(fib5(n));
System.out.println("---------------");
n = 72;
//System.out.println(fib1(n));
System.out.println(fib2(n));
System.out.println(fib3(n));
System.out.println(fib4(n));
System.out.println(fib5(n));
}
}
6.Python language implementation
(1) Recursive method
def fib_recur(n):
assert n >= 0, "n > 0"
if n <= 1:
return n
return fib_recur(n-1) + fib_recur(n-2)
for i in range(1, 20):
print(fib_recur(i), end=' ')
(2) Recursion method
def fib_loop(n):
a, b = 0, 1
for i in range(n + 1):
a, b = b, a + b
return a
for i in range(20):
print(fib_loop(i), end=' ')
(3)Generator
def fib_loop_while(max):
a, b = 0, 1
while max > 0:
a, b = b, a + b
max -= 1
yield a
for i in fib_loop_while(10):
print(i)
(4) Class implements internal magic method
class Fibonacci(object):
"""Fibonacci Sequence Iterator"""
def __init__(self, n):
"""
:param n:int refers to the number of generated arrays
"""
self.n = n
# Save the data of the currently generated data column, the properties in the generator, the recording position, and the data at the next position
self.current = 0
# Two initial values
self.a = 0
self.b = 1
def __next__(self):
"""When called using the next() function, the next number will be obtained"""
if self.current < self.n:
self.a, self.b = self.b, self.a + self.b
self.current + = 1
return self.a
else:
raise StopIteration
def __iter__(self):
"""The __iter__ of the iterator can just return itself"""
return self
if __name__ == '__main__':
fib = Fibonacci(15)
for num in fib:
print(num)
(5) Matrix fast power
import numpy as np
### 1
def fib_matrix(n):
for i in range(n):
res = pow((np.matrix([[1, 1], [1, 0]], dtype='int64')), i) * np.matrix([[1], [0]])
print(int(res[0][0]))
# transfer
>fib_matrix(50)
### 2
# Calculate the Fibonacci sequence using matrices
def Fibonacci_Matrix_tool(n):
Matrix = np.matrix("1 1;1 0", dtype='int64')
#The return is matrix type
return np.linalg.matrix_power(Matrix, n)
def Fibonacci_Matrix(n):
result_list = []
for i in range(0, n):
result_list.append(np.array(Fibonacci_Matrix_tool(i))[0][0])
return result_list
# transfer
> Fibonacci_Matrix(50)
### pow is faster than double**, np.linalg.matrix_power is also a method