递归的相关知识(Java)全面版
目录
递归定义:
二分查找:
代码:
冒泡排序:
代码:
插入排序:
代码:
斐波那契数列:
代码:
优化的代码:
汉诺塔:
代码:
杨辉三角:
代码:
优化的代码Demo1:二维数组
优化的代码Demo2:一维数组
递归定义:
在计算机科学中，递归是一种核心概念，通常用于定义或描述一个过程或函数。在这个过程中，函数直接或间接地调用自身，这被看作是一种通过重复将问题分解为同类的子问题而解决问题的方法。
二分查找:
是一种在有序数组中查找特定元素的算法。 它通过不断比较中间元素与目标元素的大小，逐步缩小查找范围
代码:
private static int binarySearch(int[] array, int target, int i, int j){
if(i>j)
return -1;
int mid=(i+j)>>>1;
if(target<array[mid]){
return binarySearch(array,target,i,mid-1);
}else if(target>array[mid]){
return binarySearch(array,target,mid+1,j);
}else{
return mid;
}
}冒泡排序:
相邻的两个元素比较,如果前一个元素大于后一个元素,则交换位置
代码:
private static void bubble(int []arr,int j){
if(j==0){
return;
}
int x=0;//记录未排序右边界
for(int i=0;i<j;i++){
if(arr[i]>arr[i+1]){
int temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
x=i;
}
}
bubble(arr,x);
}插入排序:
通过比较相邻元素的顺序，找到每个元素应该插入的位置，并将其插入,(数组的第二个元素开始) 类似于扑克牌排序,从后往前排
代码:
public static void insertionSort(int[] arr)
{
insertion(arr,1);
}
private static void insertion(int[] arr,int low){
if(low==arr.length){
return;
}
int t=arr[low];
int i=low-1;
while(i>=0&&t<arr[i]){
arr[i+1]=arr[i];
i--;
}
if(i+1!=low)
arr[i+1]=t;//找到插入位置
insertion(arr,low+1);
}
斐波那契数列:
斐波那契数列是一个无限序列，其前几项为0、1、1、2、3、5、8、13、21、34、...，从第三项开始，每一项都等于前两项之和。 变体1(兔子),变体2(青蛙跳楼梯)
代码:
public static int f(int n){
if(n==0)
return 0;
else if(n==1)
return 1;
else return f(n-1)+f(n-2);
}优化的代码:
用空间复杂度代替时间复杂度
public static int fibonacci(int n){
int []cache=new int[n+1];
Arrays.fill(cache,-1);//给数组中的每一个元素初始为-1
cache[0]=0;
cache[1]=1;
return f(n,cache);
}
private static int f(int n,int cache[]){
if(cache[n]!=-1){
return cache[n];
}
int x=f(n-1,cache);
int y=f(n-2,cache);
cache[n]=x+y;
return cache[n];
}汉诺塔:
将所有圆盘从一根木桩移动到另一根木桩上，且在移动过程中大的圆盘不能放在小的圆盘上面，每次只能移动一个圆盘，可以利用中间的一根木桩作为辅助。
代码:
import java.util.LinkedList;
public class HannoTower {
static LinkedList<Integer> a =new LinkedList<>();
static LinkedList<Integer> b =new LinkedList<>();
static LinkedList<Integer> c =new LinkedList<>();
public static void init(int n){//初始化给a
for (int i =n ; i >=1 ; i--) {
a.addLast(i);
// a.addFirst(i);
}
}
public static void move(int n,LinkedList<Integer> a,
LinkedList<Integer> b,
LinkedList<Integer> c){
if(n==0)
return;
move(n-1,a,c,b);//把a 中的元素借助b移动c
c.addLast(a.removeLast());
print();
System.out.println("----------------");
move(n - 1, b, a, c);//把b 中的元素借助a移动c
}
public static void print(){
System.out.println(a);
System.out.println(b);
System.out.println(c);
}
public static void main(String[] args) {
init(3);
print();
System.out.println("=======================");
move(3,a,b,c);
}
}
杨辉三角:
其两条斜边上都是数字1，其余的数都等于它肩上的两个数字相加。
代码:
public static int element(int i,int j){
if(j==0||i==j){
return 1;
}
return element(i-1,j-1)+element(i-1,j);
}
private static void printSpace(int n,int i){//打印空格
int num=(n-i-1)*2;
for(int j=0;j<num;j++){
System.out.print(" ");
}
}
public static void print(int n){
for(int i=0;i<n;i++){
printSpace(n,i);
for(int j=0;j<=i;j++){
System.out.printf("%-4d",element(i,j));
}
System.out.println();
}
}优化的代码Demo1:二维数组
public static int element1(int [][] arr,int i,int j){
if(arr[i][j]>0){
return arr[i][j];
}
if(j==0||i==j){
arr[i][j]=1;
return arr[i][j];
}
arr[i][j]=element1(arr,i-1,j-1)+element1(arr,i-1,j);
return arr[i][j] ;
}
private static void printSpace(int n,int i){//打印空格
int num=(n-i-1)*2;
for(int j=0;j<num;j++){
System.out.print(" ");
}
}
public static void print1(int n){
int [][]arr=new int[n][];
for(int i=0;i<n;i++){
arr[i]=new int[i+1];
printSpace(n,i);
for(int j=0;j<=i;j++){
System.out.printf("%-4d",element1(arr,i,j));
}
System.out.println();
}
}优化的代码Demo2:一维数组
private static void printSpace(int n,int i){//打印空格
int num=(n-i-1)*2;
for(int j=0;j<num;j++){
System.out.print(" ");
}
}
public static void createRow(int []row,int i){
if(i==0){
row[0]=1;
}
for (int j = i; j >0 ; j--) {
row[j]=row[j]+row[j-1];
}
}
public static void print1(int n){
int []row=new int[n];
for(int i=0;i<n;i++){
createRow(row,i);
printSpace(n,i);
for(int j=0;j<=i;j++){
System.out.printf("%-4d",row[j]);
}
System.out.println();
}
}