🌙递归练习
代码示例1
按顺序打印一个数字的每一位(例如 1234 打印出 1 2 3 4)
public static void print(int num) { if (num > 9) { print(num / 10); } System.out.println(num % 10); }
代码示例2
递归求 1 + 2 + 3 + … + 10
public static int sum(int num) { if (num == 1) { return 1; } return num + sum(num - 1); }
代码示例3
写一个递归方法，输入一个非负整数，返回组成它的数字之和. 例如，输入 1729, 则应该返回
1+7+2+9，它的和是19
public static int sum(int num) { if (num < 10) { return num; } return num % 10 + sum(num / 10); }
代码示例4 （敲重点！！敲重点！！敲重点！！）
求斐波那契数列的第n项【斐波那契数列是一组第一位和第二位为1，从第三位开始，后一位是前两位和的一组递增数列，像这样的：0、1、1、2、3、5、8、13、21、34、55…】
方法一：循环
这种解法是比较高效的一种解法
时间复杂度O(n),空间复杂度O(1)
import java.util.Scanner; public class 斐波那契数 {//时间复杂度O(n),空间复杂度O(1) public static void main(String[] args) { Scanner scn = new Scanner(System.in); int n = scn.nextInt(); int a = 0; int b = 1; int tmp = 0; if (n==1){ System.out.println(0); } else if (n==2){ System.out.println(1); } else if (n>2) { for ( int i = 3; i <= n; i++ ) { tmp = a+b; a = b; b = tmp; } System.out.println(b); } } }
方法二：递归
此解法思维方式非常简单
但是时间复杂度特别高，时间复杂度O(2^n),空间复杂度O(n)
不建议采用这种方法。
import java.util.Scanner; public class 递归求斐波那契数列 {//时间复杂度O(2^N),空间复杂度O(n) public static int count = 0; public static int Fib(int n) { if (n==1) return 0; else if (n==2||n==3) return 1; else if (n==4) count++; return Fib(n-1)+Fib(n-2); } public static void main(String[] args) { Scanner scn = new Scanner(System.in); while (scn.hasNextInt()) { int n = scn.nextInt(); System.out.println("第"+n+"个斐波那契数是"+Fib(n)); System.out.println("递归了"+count+"次"); count = 0; } } }
可以看到当求第40个斐波那契数时，重复次数高达24157817次
方法三：高效递归
如果说前一种递归解法是由后向前计算，那么这种解法就是由前向后计算了，
这种递归方式属于尾递归，因此在进行递归时函数只会使用第一次压栈所开辟的栈空间，在一个栈空间内循环，而不会开辟别的栈空间
所以这种方式时间复杂度为O(n)，空间复杂度为O(1)是一种非常高效的递归方式。
import java.util.Scanner; public class 高效递归求斐波那契数列 { //时间复杂度O(n)，空间复杂度O(1) public static int Fib(int first,int sec,int n) { if (n==1) return first; else return Fib(sec,first+sec,n-1); } public static void main(String[] args) { Scanner scn = new Scanner(System.in); while (scn.hasNextInt()) { int n = scn.nextInt(); System.out.println("第"+n+"个斐波那契数是"+Fib(0,1,n)); } } }
🌙递归总结
递归是一种重要的编程解决问题的方式.
有些问题天然就是使用递归方式定义的(例如斐波那契数列, 二叉树等), 此时使用递归来解就很容易.
有些问题使用递归和使用非递归(循环)都可以解决. 那么此时更推荐使用循环, 相比于递归, 非递归程序更加高效.
