青岛大学_王卓老师【数据结构与算法】Week05_11_栈与递归

这篇具有很好参考价值的文章主要介绍了青岛大学_王卓老师【数据结构与算法】Week05_11_栈与递归_学习笔记。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

本文是个人学习笔记，素材来自青岛大学王卓老师的教学视频。

一方面用于学习记录与分享，

另一方面是想让更多的人看到这么好的《数据结构与算法》的学习视频。

如有侵权，请留言作删文处理。

课程视频链接：

数据结构与算法基础–第05周11–3.4栈和递归

📚 【Week05】11_栈与递归

递归的定义

(1) 若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的。

(2) 若一个过程直接或间接地调用自己，则称这个过程是递归的过程。

例如：递归求 n 的阶乘

long Fact(long n){
	if(n == 0)
        return 1;
    else
        return (n * Fact(n-1));
}

以下三种情况尝尝用到递归方法

(1) 递归定义的数学函数

阶乘函数

青岛大学_王卓老师【数据结构与算法】Week05_11_栈与递归_学习笔记,【数据结构与算法】王卓老师,学习,笔记

2 阶 Fibonaci 数列

青岛大学_王卓老师【数据结构与算法】Week05_11_栈与递归_学习笔记,【数据结构与算法】王卓老师,学习,笔记

(2) 具有递归特性的数据结构

青岛大学_王卓老师【数据结构与算法】Week05_11_栈与递归_学习笔记,【数据结构与算法】王卓老师,学习,笔记

(3) 可递归求解的问题

迷宫问题

Hanoi 塔问题

递归问题——用分治法求解

分治法

对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解

必备的三个条件

(1) 能够将一个问题转变为一个新问题，且新问题与原问题的解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化且有规律的

(2) 可以通过上述转化而使问题简化

(3) 必须有一个明确的递归出口，或称递归的边界

分治法求解递归问题算法的一般形式

void p(参数表){
    if(递归结束条件)
        可直接求解步骤;	// -- 基本项
    else
        p(较小的参数);	 // -- 归纳项
}

例如

long Fact(long n){
	if(n == 0)
        return 1;					// -- 基本项
    else
        return (n * Fact(n-1));		// -- 归纳项
}

函数调用过程

调用前，系统完成：

(1) 将实参，返回地址等传递给被调用函数

(2) 为被调用函数的局部变量分配存储区

(3) 将控制转移到被调用函数的入口

调用后，系统完成：

(1) 保存被调用函数的计算结果

(2) 释放被调用函数的数据区

(3) 依照被调用函数保存的返回地址将控制转移到调用函数

当多个函数构成嵌套调用时：

int main(void){
    ...;
    y = fact(3);
    ...;       
}

double fact(int n){
    ...;
    z = mypow(3.5, 2);
    ...;
}

double mppow(double x, int n){
    ...;
}

遵循后调用的先返回

求解阶乘 n ! 的过程

long Fact(long n){
	if(n == 0)
        return 1;
    else
        return (n * Fact(n-1));
}

青岛大学_王卓老师【数据结构与算法】Week05_11_栈与递归_学习笔记,【数据结构与算法】王卓老师,学习,笔记

递归函数调用的实现

青岛大学_王卓老师【数据结构与算法】Week05_11_栈与递归_学习笔记,【数据结构与算法】王卓老师,学习,笔记

进行 fact(4) 调用的系统栈的变化状态

青岛大学_王卓老师【数据结构与算法】Week05_11_栈与递归_学习笔记,【数据结构与算法】王卓老师,学习,笔记

递归的优缺点

优点：结构清晰，程序易读

缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息。时间开销大。

递归 -> 非递归

方法1：尾递归、单向递归 -> 循环结构

方法2：自用栈模拟系统的运行时栈

尾递归 -> 循环结构

long Fact(long n){
	if(n == 0)
        return 1;
    else
        return (n * Fact(n-1));
}

转换为循环

long Fact(long n){
	t = 1;
	for(int i=1; i<n; i++){
		t = t*i;
	}
    return t;
}

单向递归 -> 循环结构

虽然有一处以上的递归调用语句，但各次递归调用语句的参数只和主调函数有关，相互之间参数无关，

并且这些递归调用语句处于算法的最后。

// Fibonacci 数列
long Fib(long n){
    if(n == 1 || n == 2)
        return 1;
    else 
        return (Fib(n-1) + Fib(n-2));
}

转换为

// Fibonacci 数列
long Fib(long n){
    if(n == 1 || n == 2)
        return 1;
    else {
        t1 = 1;
        t2 = 1;
        for(i=3; i<n; i++){
            t3 = t1 + t2;
            t1 = t2;
            t2 = t3;
        }
        
        return t3;
    }
}