递归和回溯

阳光穿透心脏的1/2处 2022-02-03 15:57 212阅读 0赞

## 递归 ##

任何调用自身的函数称为**递归**。递归的要点在于，递归函数调用自身去解决一个规模比原始问题要小一些的问题。

**递归函数的格式**

*  函数不在递归地情况称作基本情形（base case,也称基本情况）。
 *  函数调用自身来执行子任务的情况就称作递归情形（recursive case）。

if (判断是否为基本情形)
        return 该基本情形时的函数值
    else if (判断是否为另一种基本情形)
        return 该基本情形时的函数值
    //递归情形
    else return (执行某些工作并递归调用)

\*\*例：\*\*n!等于n~1之间所有整数的乘积，起递归定义如下

n! = 1 n=0|1 （基本情形）

n! = n\*(n-1)! n>0 （递归情形）

代码如下

public static int Fact(int n) { 
    		// 基本情形：当参数为0或1时，返回1
    		if(n == 1)
    			return 1;
    		else if(n == 0)
    			return 1;
    		// 递归情形：返回n*(n-1)!
    		else 
    			return n * Fact(n - 1);
    	}

**递归和内存可视化**

public static int Print(int n) { 
    		if (n == 0)
    			return 0;
    		else { 
    			System.out.println(n);
    			return Print(n - 1);
    		}
    	}

![Snipaste\_2019-05-08\_21-25-48.jpg][Snipaste_2019-05-08_21-25-48.jpg]  
![Snipaste\_2019-05-08\_21-26-04.jpg][Snipaste_2019-05-08_21-26-04.jpg]

## 回溯 ##

回溯是一种采用分治策略进行穷举搜索的方法。

[Snipaste_2019-05-08_21-25-48.jpg]: https://i.loli.net/2019/05/08/5cd2d918a5e5b.jpg
[Snipaste_2019-05-08_21-26-04.jpg]: https://i.loli.net/2019/05/08/5cd2d91a22434.jpg

发表评论取消回复

表情：

评论列表（有 0 条评论，212人围观）

还没有评论，来说两句吧...

相关阅读

相关 8皇后问题-递归-回溯（Java）

目录 5.6 递归-八皇后问题（回溯算法） 5.6.1 解题思路 5.6.2 代码实现

忘是亡心i/ 2024年04月08日 12:21/ 0 赞/ 73 阅读

相关使用递归进行回溯

使用递归进行回溯回溯是一种递归地解决问题的算法技术，它试图逐步建立一个解决方案，一次一个，删除那些在任何时间点上不能满足问题约束的解决方案（这里的时间是指到达搜索树的任何一

怼烎@/ 2024年04月01日 13:29/ 0 赞/ 71 阅读

相关北大硕士LeetCode算法专题课--递归和回溯

算法专题课 [ 北大硕士LeetCode算法专题课-栈、队列相关问题\_骨灰级收藏家的博客-CSDN博客][_LeetCode_-_-CSDN] [

浅浅的花香味﹌/ 2024年03月29日 14:07/ 0 赞/ 63 阅读

相关【算法系列篇】递归、搜索和回溯（四）

![在这里插入图片描述][9b58a34c5a614307b1477df857be4201.gif_pic_center] 文章目录前言什么是决策

青旅半醒/ 2024年02月05日 16:18/ 0 赞/ 32 阅读

相关【算法系列篇】递归、搜索和回溯（三）

![在这里插入图片描述][ad21b455de0b4510ace6d27c2f7079b0.gif_pic_center] 文章目录前言什么是二叉

刺骨的言语ヽ痛彻心扉/ 2024年02月05日 15:05/ 0 赞/ 37 阅读

相关【算法系列篇】递归、搜索和回溯（二）

![在这里插入图片描述][b90ac447efcc4bb993f982f0c3d262fe.gif_pic_center] 文章目录前言 1. 两两

Bertha 。/ 2024年02月05日 13:44/ 0 赞/ 23 阅读

相关递归-八皇后问题（回溯算法）

一：八皇后问题八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848 年提出：在 8×8 格的国际象棋上摆放八个皇

心已赠人/ 2022年11月07日 04:16/ 0 赞/ 235 阅读

相关递归与回溯

非递归回溯算法框架： int a[n], i; 初始化数组a[n]; i = 1; while ((i>0(有路可走) && （未达到

喜欢ヅ旅行/ 2022年06月06日 00:55/ 0 赞/ 178 阅读

相关 java算法- 递归回溯法

1、随机输入手机上的数字，使字母组成不同的组合 public class base01 { private String lette

朴灿烈づ我的快乐病毒、/ 2022年04月24日 10:44/ 0 赞/ 247 阅读

相关递归和回溯

递归任何调用自身的函数称为递归。递归的要点在于，递归函数调用自身去解决一个规模比原始问题要小一些的问题。递归函数的格式函数不在递归地情况称作基本情形（ba

阳光穿透心脏的1/2处/ 2022年02月03日 15:57/ 0 赞/ 213 阅读