数据结构学习--递归简述

Leefs 2020-01-30 PM 1778℃ 0条

# 数据结构学习--递归简述

### 一、递归应用场景

看个实际应用场景，迷宫问题(回溯)， 递归(Recursion)

![10.递归简述01.png][1]

### 二、递归的概念

简单的说：递归就是方法自己调用自己，每次调用时传入不同的变量，递归有助于编程者解决复杂的问题，同时可以让代码变得简洁。

### 三、递归调用机制

两个递归调用案例：

（1）打印问题

（2）阶乘问题

使用图解方式说明递归调用机制

![10.递归简述02.png][2]

**代码示例**

```java
public class RecursionTest {
    public static void main(String[] args) {

test(4);
        int res = factorial(3);
        System.out.println("res="+res);
    }
    //打印问题
    public static void test(int n){
        if(n>2){
            test(n - 1);
        }
        System.out.println("n="+n);
    }
    //阶乘问题
    public static int factorial(int n){
        if(n == 1){
            return 1;
        }else{
            return factorial(n-1)*n;
        }
    }
}
```

> 运行结果

```
n=2
n=3
n=4
res=6
```
### 四、递归能解决的问题

> (1)各种数学问题如: 8皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题(google编程大赛)
>
> (2)各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等.
>
> (3)将用栈解决的问题-->递归代码比较简洁

### 五、递归需要遵守的重要规则

（1）执行一个方法时，就创建一个新的受保护的独立空间（栈空间）

（2）方法的局部变量是独立的，不会相互影响，比如n变量

（3）如果方法中使用的是引用类型变量（比如数组），就会共享该引用类型的数据

（4）递归必须向退出**递归的条件逼近**，否则就是无限递归，出现`StackOverflowError`

（5）当一个方法执行完毕，或者遇到return,就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。

[1]: https://lilinchao.com/usr/uploads/2020/01/1312568681.png
  [2]: https://lilinchao.com/usr/uploads/2020/01/342897570.png

标签: 递归, 数据结构

非特殊说明，本博所有文章均为博主原创。

如若转载，请注明出处：https://lilinchao.com/archives/507.html

上一篇数据结构学习--中缀表达式转换为后缀表达式

下一篇数据结构学习--递归-迷宫问题

数据结构学习--递归简述

评论已关闭

栏目分类

标签云

友情链接申请

数据结构学习--递归简述

评论已关闭

 栏目分类

标签云

友情链接申请

栏目分类

标签云

友情链接申请