递归的几种形式

2023-08-06 06:10| 来源: 网络整理| 查看: 265

递归的几种形式

文章目录递归的几种形式前言一、递归是什么？二、递归三要素：三、递归算法编程模型应用总结##

前言

：一直觉得递归很难理解，刚学的时候总分不清怎么调用，在这里为大家分享下我学习递归时的笔力

一、递归是什么？

递归是指在函数的定义中使用函数自身的方法递归问题必须可以分解为若干个规模较小，与原文题形式相同的子问题，这些子问题可以用相同的解题思路来解决。格外重要的是递归必须有结束条件。

二、递归三要素：

1.明确递归终止条件； 2.给出递归终止时的处理方法； 3.提取重复的逻辑，缩小问题规模。

三、递归算法编程模型

1.在递去的过程中解决问题 function recursion(大规模){ if (end_condition){ // 明确的递归终止条件 end; // 简单情景 }else{ // 在将问题转换为子问题的每一步，解决该步中剩余部分的问题 solve; // 递去 recursion(小规模); // 递到最深处后，不断地归来 } } 2.在归来的过程中解决问题 function recursion(大规模){ if (end_condition){ // 明确的递归终止条件 end; // 简单情景 }else{ // 先将问题全部描述展开，再由尽头“返回”依次解决每步中剩余部分的问题 recursion(小规模); // 递去 solve; // 归来 } }

应用

1.问题的定义是按递归定义的（阶乘，Fibonaci数列）代码如下（示例）：

public class int jiecheng(int n) { if(n==1) return 1; return n*jiecheng(n-1); } 斐波那契 public static int f(int n) { if(n==1||n==2) { return 1; } return f(n-1)+f(n-2); }

代码如下（示例）：字符串全排列

//from 起始下标，to终止下标 public static void Z(char[] s,int from,int to) { if(s!=null&&to>=from&&to=0) { if(from==to) { system.out.println(s); } else { for(int i=from;i char temp=s[from]; s[from]=s[to]; s[to]=temp; }

第二类问题：问题解法按递归算法实现

汉罗塔问题

public class hanoitower { //num数量，from 初始地址，inter 中转，to目的地 public static void moveDish(int level, char from, char inter, char to) { if (level == 1) { // 递归终止条件 System.out.println("从" + from + " 移动盘子" + level + " 号到" + to); } else { // 递归调用：将level-1个盘子从from移到inter(不是一次性移动，每次只能移动一个盘子,其中to用于周转) moveDish(level - 1, from, to, inter); // 递归调用，缩小问题的规模 // 将第level个盘子从A座移到C座 System.out.println("从" + from + " 移动盘子" + level + " 号到" + to); // 递归调用：将level-1个盘子从inter移到to,from 用于周转 moveDish(level - 1, inter, from, to); // 递归调用，缩小问题的规模 } } public static void main(String[] args) { int nDisks = 30; moveDish(nDisks, 'A', 'B', 'C'); }

第三类：数据的结构是按递归的二叉树深度

public class BinaryTreeDepth { /** * @description 返回二叉数的深度 * @author rico * @param t * @return */ public static int getTreeDepth(Tree t) { // 树为空 if (t == null) // 递归终止条件 return 0; int left = getTreeDepth(t.left); // 递归求左子树深度，缩小问题的规模 int right = getTreeDepth(t.left); // 递归求右子树深度，缩小问题的规模 return left > right ? left + 1 : right + 1; } } 总结## 以上就是今天要讲的内容，本文仅仅简单介绍了递归的使用希望对你有所帮助

【本文地址】

公司简介

联系我们