递归实现斐波那契数列

首先我说一下不适用递归是什么样子：我们只使用一个简单的循环：

import java.util.Scanner;/*** @author ${范涛之}* @Description* @create 2021-10-30 13:07*//*** 不使用递归*/
public class FibonacciSequence {public static void main(String[] args) {long num1 = 0;long num2 = 1;long num = 1;Scanner scanner = new Scanner(System.in);System.out.println("请输入一个数字");long number = scanner.nextInt();System.out.println(num1);System.out.println(num);long result = 0;for (int i = 3; i <number; i++) {num = num1+num2;num1 = num2;num2 = num;System.out.println(num);result += num;}System.out.println("前"+number+"个数字的和为"+result);}
}

使用递归：

import java.util.Scanner;/*** @author ${范涛之}* @Description* @create 2021-10-30 13:56*/
public class FibonacciSequence1 {/**** 使用递归，自己调用自己**/public  static  long  fibonacciSequence(int i){if (i<=1)return i;return fibonacciSequence(i-1)+fibonacciSequence(i-2);}public static void main(String[] args) {long sum = 0;Scanner scanner = new Scanner(System.in);System.out.println("请输入一个数字");int number = scanner.nextInt();for (int i = 0; i <number; i++) {System.out.println(fibonacciSequence(i));sum +=fibonacciSequence(i);}System.out.println("前"+number+"个数字的和为："+sum);}}

自己遇到的一些小问题或发现：首先自己第一次使用int,然后最后发现太小了！

然后说一下自己的一个发现：就是使用循环可以一下子就输出结果，但是递归就不能，递归输出的速度要慢很多！

1.所谓的递归慢到底是什么原因呢？
大家都知道递归的实现是通过调用函数本身，函数调用的时候，每次调用时要做地址保存，参数传递等，这是通过一个递归工作栈实现的。具体是每次调用函数本身要保存的内容包括：局部变量、形参、调用函数地址、返回值。那么，如果递归调用N次，就要分配N局部变量、N形参、N调用函数地址、N返回值。这势必是影响效率的。

10的阶乘：

/*** @author ${范涛之}* @Description* @create 2021-10-30 14:04*//*** 计算10的阶乘*/
public class Factorial {public  static int factorial( int i){if (i==1)return 1;else return i*factorial(i-1);}public static void main(String[] args) {System.out.println(factorial(10));}}

对数组[8, 2, 11, 9, 1, 5, 3]使用二分算法进行排序

(0+9)/2=4.5=4

5<6

例图

排序思路：

 /*** 二分法排序<br>* 根据排序原则，每次我们都是在一个有序序列中插入一个新的数字<br>* 那么我们可以将这个有序序列进行二分。<br>* 左游标left为0，右游标right为i-1(i是这个数字在原数组中的位置)<br>* middle初始为。<br>* 当left<=right时<br>* middle是left和right的中值。<br>* 我们作如下操作。如果array[i]的值比array[middle]值大。<br>* 那么我们就移动左游标令值为middle+1<br>* 负责就移动右游标为middle-1<br>* 移动完成后,我们需要将i-1到left之间的值进行依次向后移动给array[i]空出一个位置然后将array[i]插入* <p style="color:red">时间复杂度n</p>*/

package first;import org.junit.jupiter.api.Test;/*** @author ${范涛之}* @Description* @create 2021-10-30 17:27*/
public class First {/*** 二分法排序<br>* 根据排序原则，每次我们都是在一个有序序列中插入一个新的数字<br>* 那么我们可以将这个有序序列进行二分。<br>* 左游标left为0，右游标right为i-1(i是这个数字在原数组中的位置)<br>* middle初始为。<br>* 当left<=right时<br>* middle是left和right的中值。<br>* 我们作如下操作。如果array[i]的值比array[middle]值大。<br>* 那么我们就移动左游标令值为middle+1<br>* 负责就移动右游标为middle-1<br>* 移动完成后,我们需要将i-1到left之间的值进行依次向后移动给array[i]空出一个位置然后将array[i]插入* <p style="color:red">时间复杂度n</p>*/public static int[] binaryInsertSort(int[] array){for(int i = 0;i<array.length;i++){int temp = array[i];//待插入到前面有序序列的值int left = 0;//有序序列的左侧int right = i-1;//有序序列的右侧int middle = 0;//有序序列的中间while(left <= right){middle = (left + right)/2;//赋值if(temp<array[middle]){right = middle-1;}else{left = middle + 1;}}for(int j = i-1;j>=left;j--){//从i-1到left依次向后移动一位,等待temp值插入array[j+1] = array[j];}if(left != i ){array[left] = temp;}}return array;}public static void main(String[] args) {int arr[] = new int[]{8, 2, 11, 9, 1, 5, 3};binaryInsertSort(arr);for (int i = 0; i <arr.length; i++) {System.out.println(arr[i]);}}}

一些其他的排序方法：

/*** @author ${范涛之}* @Description* @create 2021-10-30 15:22*/public class ArrayBinarySearch {/***  冒泡法排序(从小到大)* @param a 需要排序的数组* @return  排序完成后的数组*/public static int[] sort1(int[] a) {for(int i = 0;i < a.length-1;i++) {for(int j = 0;j < a.length-1-i;j++) {if(a[j]>a[j+1]) {int temp;temp = a[j];a[j] = a[j+1];a[j+1] = temp;}}}return a;}/***  选择法排序* @param a* @return*/public static int[] sort2(int[] a) {for(int i = 0;i < a.length;i++) {for(int j = i+1;j < a.length;j++) {if(a[i]>a[j]) {int temp;temp = a[i];a[i] = a[j];a[j] = temp;}}}return a;}/***  二分法查找* @param a 需要进行检索的数组* @param idx 需要检索的值* @return 检索结果（该值下标或-1：未找到）*/public static int index(int[] a,int idx) {int min = 0;int max = a.length-1;while(min <= max) {int middle = (min + max)/2;if(a[middle] == idx) {return middle;}if(idx > a[middle]) {min = middle+1;}else {max = middle - 1;}}return -1;}/*下面对以上方法进行测试*/public static void main(String[] args) {int[] a = {3,10,15,11,6,7};for(int x:sort1(a)) {System.out.print(x + "\t");}System.out.println();int[] b = {5,1,3,7,2,44,12,3};for(int y:sort2(b)) {System.out.print(y + "\t");}System.out.println();int[] c = sort2(b);System.out.println(index(c,22));}/*** output:* 3    6   7   10  11  15* 1    2   3   5   7   12  44* -1*/}

和数分解：把一个数分解成任意几个数的和，并把所有的可能性都列出来

/*** @author ${范涛之}* @Description* @create 2021-10-30 18:24*/
import java.util.Scanner;public class Test {static int[] arr=new int[10000];static Scanner input=new Scanner(System.in);static int num;public static void main(String[] args) {System.out.println("请输入一个要分解的数:");num=input.nextInt();search(num,1,0);}private static void search(int n, int s, int x) {if(n>0) {for(int i=s;i<=n;i++) {arr[x]=i;search(n-i,i,x+1);}return;}System.out.print(num+"="+arr[0]);for(int i=1;i<x;i++) {System.out.print("+"+arr[i]);}System.out.println();}}