目录

 ☕前言☕

            🍔🍔一、递归求 N 的阶乘

            🍞🍞二、按顺序打印数字的每一位（例如 1234 打印出 1 2 3 4）

            🍚🍚三、递归求 1 + 2 + 3 + ... + 10

            🍺​​​​​​​🍺四、输入一个非负整数，返回组成它的数字之和

            🍜​​​​​​​🍜五、递归顺序打印数组的每个元素

            🧀​​​​​​​🧀六、递归逆序打印数组的每个元素

            🥩​​​​​​​🥩七、求斐波那契数列的第 N 项

 🥤总结

前言

对于 递归的知识点，看着不难，但是做起来总是感觉 脑袋晕乎乎的。

所以，还是需要经过大量的练习题 来巩固自己对知识的理解......

递归的主要难点在于：如何推导一个递推公式，以及 如何找到一个终止条件；

如果终止条件找错了，很可能会出现 栈溢出 的情况；

从某种意义上来看，终止条件 其实就是起始条件。

搞清楚了这两点，递归题目就很容易的就做出来了。

一、递归求 N 的阶乘

比如说，

5! = 5*4!       4! = 4*3!       3! = 3*2!       2!=2*1!       1!=1

由此可以推导出，N! = N*(N-1)! 

public class TestDemo_2 {    public static int fac1(int n){ if(n == 1){     return 1; } int tmp = n * fac1(n-1); return tmp;    }    public static void main(String[] args) { int ret = fac1(5); System.out.println(ret);    }}

 小小总结一下:

递归的思考 是 横向思考，代码的执行 是 纵向执行。

即：自己去思考递归的时候，去横向思考，不用管代码是怎么执行的，代码的执行交给计算机即可，我们只要想明白 递推的公式、此问题的思路即可。

比如说，我们要知道 N 的阶乘，只需要知道 N!=N*(N-1)! 即可:

二、按顺序打印数字的每一位（例如 1234 打印出 1 2 3 4）

打印出每一位 首先就要取出每一位。

比如说，1234

       1234%10==4

       123%10==3

       12%10==2

       1%10==1

由此可以推出，如果N只有1位数，那么就直接打印出这一位数即可，如果N有两位数及其以上，那么就需要 通过不断的 除10模10 算出一位数，再打印出去即可。

public class TestDemo_2 {    public static void func2(int n){ if(n<=9){     System.out.println(n);     return; } func2(n/10); System.out.println(n%10);    }    public static void main(String[] args) { func2(123);    }}

【说明】所要的东西在大多数情况下 都是 从后往前才能去实现的。 

三、递归求 1 + 2 + 3 + ... + 10

public class TestDemo_2 {    public static int sum(int n){ if(n==1){     return 1; } int tmp=n+sum(n-1); return tmp;    }    public static void main(String[] args) { System.out.println(sum(10));    }}

举个1+2+3的例子图示：

四、输入一个非负整数，返回组成它的数字之和

例如，输入 1729, 则应该返回1+7+2+9， 它的和是19。

public class TestDemo_2 {    public static int sumE(int n){ if(n<=9){     return n; } int tmp = n%10 +sumE(n/10); return tmp;    }    public static void main(String[] args) { System.out.println(sumE(1729));    }}

五、递归顺序打印数组的每个元素

public class TestDemo_2 {    public static void print(int[] array,int len){ if(len==1){     System.out.println(array[len-1]);     return; } print(array,len-1); System.out.println(array[len-1]);    }    public static void main(String[] args) { int[] array = {1,2,3}; print(array, array.length);    }}

六、递归逆序打印数组的每个元素

public class TestDemo_2 {    public static void print(int[] array,int len){ if(len==1){     System.out.println(array[len-1]);     return; } System.out.println(array[len-1]); print(array,len-1);    }    public static void main(String[] args) { int[] array = {1,2,3,4,5}; print(array, array.length);    }}

七、求斐波那契数列的第 N 项

斐波那契数列介绍

public class TestDemo_2 {    public static int fib(int n){ if(n==1){     return 0; } if(n==2){     return 1; } int tmp = fib(n-1)+fib(n-2); return tmp;    }    public static void main(String[] args) { System.out.println(fib(1)); System.out.println(fib(2)); System.out.println(fib(3)); System.out.println(fib(43));    }}

当n数字较大时，程序执行速度极慢，原因是进行了大量的重复运算，因此更推荐 使用循环 做斐波那契数列。

递归的优点：代码函数少、逻辑比较清楚；

            缺点：理解起来比较困难、浪费的空间多。

循环的优点：理解起来简单；

            缺点：代码行数较多。

循环解决 斐波那契问题示例代码：

public class TestDemo_2 {    public static int fib(int n){ if (n==1){     return 0; } if (n==2){     return 1; } int f1 = 0; int f2 = 1; int f3 = 0; for (int i = 3; i <= n; i++) {     f3 = f1 + f2;     f1 = f2;     f2 = f3; } return f3;    }    public static void main(String[] args) { System.out.println(fib(1)); System.out.println(fib(2)); System.out.println(fib(3)); System.out.println(fib(4)); System.out.println(fib(42));    }}

总结

一般的递归写法是这样的：

继续分享一下好看的图片：