代碼簡潔，但涉及到的運算，會隨著遞歸層數的增加成指數級增長

路分析：第20行20列位于45度這條線上

這條線上的數字是1 5 13 25 41...兩數之差:4 8 12 16

--->每一個都是在前面的基礎上+4，可以用遞歸或者循環

public class demo1{public static void main(String[] args){System.out.println(snack(20));}public static int snack(int n){if(n==1){return 1;}return snack(n-1)+4*(n-1);}
}

遞歸與循環的關系？

一道題，可以用遞歸解答。

1.可以換成循環解決嗎-->可以-->代碼量變多，運算資源（時間復雜度）

2.若發現題目用遞歸運行時間超出限制-->換循環 && 加字典（即動態規劃）

--->加字典eg:

斐波那契數列：fn(5)=fn(4)+fn(3) fn(4)=fn(3)+fn(2)[將fn(3)和fn(2)存起來] fn(3)可以直接得出

輾轉相除法：求最大公約數

1.兩個整數的最大公約數等于其中較小的數和兩數相除余數的最大公約數(gcd)

2.gcd(a,b)=gcd(b,a%b) (前提：a>b); 當b的值為0時，a就是要求的最大公約數

eg:

12&4=4&0=4

10&7=7&3=3&1=1&0=1

輸入兩個數，求最小公約數

法1：循環解法

public class demo2{public static void main(String[] args){//a>b  gcd(a,b)=gcd(b,a%b)int a=scan.nextInt();int b=scan.nextInt();while(b!=0){int c=a%b;a=b;b=c;}System.out.println(a);}
}

法2：遞歸解法

public class demo3{public static void main(String[] args){Scanner scanner=new Scanner(System.in);int a=scanner.nextInt();int b=scanner.nextInt();int zz=zz(a,b);System.out.println(zz);}public static int zz(int a,int b){if(b==0){return a;}int c=a%b;return zz(b,c);}
}