Java |
您所在的位置:网站首页 › 递归的方式求n代码 › Java |
文章目录
Java方法递归1.递归的概念2.递归执行过程分析3.练习题练习一练习二练习三练习四练习五练习六4. 递归小结
完!
Java方法递归
1.递归的概念
一个方法在执行过程中调用自身, 就称为 “递归”. 递归相当于数学上的 “数学归纳法”, 有一个起始条件, 然后有一个递推公式. 递归的注意点: 1.程序调用自己 2.这个递归程序一定要有一个趋近于中止的条件. 3.核心:写递归程序的时候,需要自己来推导一个递推公式. 例: 我们求 N! 起始条件: N = 1 的时候, N! 为 1. 这个起始条件相当于递归的结束条件. 递归公式: 求 N! , 直接不好求, 可以把问题转换成 N! => N * (N-1)! 代码实现: import java.util.Scanner; public static int fac(int n){ if(n==1){ return 1; } return n*fac(n-1); } public static void main5(String[] args){ Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int ret = fac(N); System.out.println(ret); } 2.递归执行过程分析递归的程序的执行过程不太容易理解, 要想理解清楚递归, 必须先理解清楚 “方法的执行过程”, 尤其是 “方法执行结束之后, 回到调用位置继续往下执行”. 下面我们通过一系列的代码练习来熟悉方法递归地使用. 3.练习题 练习一题目要求 按顺序打印一个数字的每一位(例如 1234 打印出 1 2 3 4) 实现代码 public static void print(int n){ if(n>9){ print(n/10); } System.out.print(n%10+" "); } public static void main(String[] args){ int a = 1234; print(a); } 练习二题目要求: 递归求 1 + 2 + 3 + … + 10 实现代码 public static int sumption(int n){ if(n==1){ return 1; } return n+sumption(n-1); } public static void main(String[] args) { int n = 10; int ret = sumption(n); System.out.println(ret); } 练习三题目要求: 递归求 N 的阶乘 实现代码 import java.util.Scanner; public static int fac(int n){ if(n==1){ return 1; } return n*fac(n-1); } public static void main(String[] args){ Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int ret = fac(N); System.out.println(ret); } 练习四题目要求: 求斐波那契数列的第 N 项 实现代码 import java.util.Scanner; public static int fibonaci(int n){ if(n==1){ return 0; }else if(n==2){ return 1 ; } return fibonaci(n-1)+fibonaci(n-2); } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int fib = fibonaci(n); System.out.println(fib); } 练习五题目要求 实现代码:求解汉诺塔问题(提示, 使用递归) 实现代码 public static void move(char n1,char n2){ System.out.println(n1+"->"+n2); } public static void hannoi(int n,char pos1,char pos2,char pos3){ if(n==1){ move(pos1,pos3); }else{ hannoi(n-1,pos1,pos3,pos2); move(pos1,pos3); hannoi(n-1,pos2,pos1,pos3); } } public static void main(String[] args){ int n = 3; char a='A'; char b='B'; char c='C'; hannoi(n,a,b,c); }注意点: 不了解汉诺塔游戏及解题思路的同学可以看我的往期博客——汉诺塔问题详解 练习六题目要求: 实现代码: 青蛙跳台阶问题(提示, 使用递归) 实现代码 import java.util.Scanner; public static int jump(int n){ if(n==1){ return 1; }else if(n==2){ return 2; }else{ return jump(n-1)+jump(n-2); } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int ret = jump(n); System.out.println(ret); }注意点: 不了解青蛙跳台阶游戏及解题思路的同学可以看我的往期博客——青蛙跳台阶问题 4. 递归小结递归是一种重要的编程解决问题的方式. 有些问题天然就是使用递归方式定义的(例如斐波那契数列, 二叉树等), 此时使用递归来解就很容易. 有些问题使用递归和使用非递归(循环)都可以解决. 那么此时更推荐使用循环, 相比于递归, 非递归程序更加高效. 好了,这次Java方法递归的知识就分享到这里了,希望大家多多练习,谢谢大家的欣赏! 完! |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |