/*

• 递归方法,一个方法体内调用其自身。
• 递归方法包含了一种隐式循环，它会重复执行某段代码，但这种重复执行无需循环控制；
• 递归一定要想已知方向进行，否则这种递归就变成了无穷递归，类似死循环。

*/

package com.atguigu.contact;
import java.util.*;
public class ObjectRecursion {	
public static void main(String[] args) {Scanner scan = new Scanner(System.in);//测试递归方法System.out.println(new ObjectRecursion().sumNum(100));System.out.println(new ObjectRecursion().multiplyNum(100));System.out.println(new ObjectRecursion().factorialNum(25));//如果结果超出数据类型容量，则输出0System.out.println(new ObjectRecursion().array(10));System.out.println(new ObjectRecursion().array1(10));//测试斐波那契数列int[] arr = new int[30];new ObjectRecursion().fibonacciArr(arr,30);System.out.println(Arrays.toString(arr));int[] arr1 = new int[20];new ObjectRecursion().fibonacciArr1(arr1,20);System.out.println(Arrays.toString(arr1));int[] arr2 = new int[10];new ObjectRecursion().fibonacciArr2(arr2,10);System.out.println(Arrays.toString(arr2));new ObjectRecursion().fibonacciArr3(300);//测试汉诺塔ObjectRecursion test = new ObjectRecursion();int hanoiDisk = 4;number n = new number();System.out.println(hanoiDisk + "个盘子的汉诺塔需移动" + test.hanoiTower(n,hanoiDisk,1,2,3) + "次");//测试快速排序int[] array = new int[] {23,67,1,6,23,78,99,11,66,2,71,84,19,25,45,0,-3,-23,5,90,-74};System.out.println(Arrays.toString(array));long start = System.currentTimeMillis();test.quickSort(array, 0, array.length - 1);System.out.println(Arrays.toString(array));long end = System.currentTimeMillis();System.out.println("程序2执行时间=" + ( end - start));}//递归实现累加public int sumNum(int n) {if(n == 1) {return 1;}else {return n + sumNum(n - 1);}}//递归实现累乘public int multiplyNum(int n) {if(n == 1) {return 1;}else {return n * sumNum(n - 1);}}//递归实现阶乘public long factorialNum(int n) {if(n == 1) {return 1;}else {return n * factorialNum(n - 1);}}//数组递归练习1，向左递归，递归参数n-public int array(int n) {if(n == 0) {return 1;}else if(n == 1) {return 4;}else{return array(n - 2) + 2 * array(n - 1);}}//数组递归练习2，向右递归，递归参数n+public double array1(int n) {if(n == 20) {return 1;}else if(n == 21) {return 4;}else{return array1(n + 2) - 2 * array1(n + 1);}}//递归输出斐波那契数列public int fibonacciArr(int[] arr,int n){		if(n == 1) {arr[n - 1] = 1;}else if(n == 2) {			arr[n - 1] = 1;}else {arr[n - 1] = fibonacciArr(arr,n - 1) + fibonacciArr(arr,n - 2);}	return arr[n - 1];}//循环方法输出斐波那契数列, 个数为npublic void fibonacciArr1(int[] arr,int n){	int f1 = 0;int f2 = 1;int m = n + 1;while(--m > 0) { //或者 m-- > 1f1 = f1 + f2;f2 = f1 - f2;	arr[n - m] = f1 ;}}//循环方法输出斐波那契数列，个数为npublic void fibonacciArr2(int[] arr,int n){	int f1 = 0;int f2 = 1;			for (int i = 0; i < n; i++) {			f1 = f1 + f2;f2 = f1 - f2;arr[i] = f1 ;			}}//循环方法输出斐波那契数列，最大值小于npublic int fibonacciArr3(int n){	int f1 = 0;int f2 = 1;		int i = 0;for (; f1 <= n;) {			f1 = f1 + f2;f2 = f1 - f2;i++;			}i -= 1;f1 = 0;f2 = 1;int[] arr = new int[i];for (int j = 0; j < i; j++) {f1 = f1 + f2;f2 = f1 - f2;arr[j] = f1 ;		}System.out.println("最大值小于等于" + n + "的斐波那契数列长度为" + i + "。结果如下");System.out.println(Arrays.toString(arr));return i;}//汉诺塔问题//两个盘子的情况下，1号盘移动到中间，2好盘移动到末尾，1号盘移动到末尾//三个盘子的情况下，先将12号盘按照上一步的方法移动到中间，再将3号盘移动到末尾，在将12号盘按上一步的方法移动到末尾//n个盘子的情况类似三个盘子的情况，先将n-1个盘子移动到中间，再把n号盘子移动到末尾，再把n-1个盘子移动到末尾。	public int hanoiTower(number num,int n,int start,int mid,int end) {	num.mark++;//执行一次则步骤计数加1;if(n==1) {System.out.println(n + "号盘从"+ start + "号位置" +"移动到" + end + "号位置");}else{hanoiTower(num,n-1,start,end,mid);//n-1号盘从start移动到midSystem.out.println(n + "号盘从"+ start + "号位置" +"移动到" + end + "号位置");//n号盘移动到末尾hanoiTower(num,n-1,mid,start,end);//n-1号盘从mid移动到end}return num.mark;}//递归实现快速排序算法//快速排序：随机选择一个数组元素作为基准值，遍历数组，把大于基准值的元素放到基准值右侧，小于基准值的元素放在基准值左侧，这样基准值在最终结果的位置确定下了。//对基准值左右两侧分别递归以上步骤，最终直到所有元素的最终位置被确定。public void quickSort(int[] a,int low,int high){int start = low;int end = high;int index = a[low];//基准值可以选取数组中任一位置元素while(end > start){while(end > start && a[end] >= index)//从后往前比较 ，直到找到一个元素小于基准值end--;if(a[end] <= index){//如果此时end位置的元素比基准值小则交换end(此时为找到的元素)与start(此时为基准值)的元素；int temp = a[end];a[end] = a[start];a[start] = temp;}while(end > start && a[start] <= index)//从前往后比较，直到找到一个元素大于基准值start++;if(a[start] >= index){//如果此时start位置的元素比基准值大则交换start(此时为找到的元素)与end(此时为基准值)位置的元素；int temp = a[start];a[start] = a[end];a[end] = temp;}//第一次循环比较结束，基准值的索引位置确定。左边都小于基准值，右边都大于基准值，但是两边的数列顺序还未排好。}//递归步骤if(start > low) {quickSort(a,low,start - 1);//左边从第一个索引到基准值索引-1}if(end < high) {quickSort(a,end + 1,high);//右边从基准值索引+1到最后一个}}	     }
//创建类number为汉诺塔问题计数准备
class  number{int mark;
}