栈与递归

递归的基本概念

递归的定义:

  • 若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的;
  • 若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。

例如:递归求 n 的阶乘

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

递归的应用

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

  • 递归定义的数学函数

阶乘函数:

$$ Fact = \begin{cases} 1 &若 n=0 \\ n\cdot Fact(n-1) &若 n>0 \\ \end{cases} $$

2阶Fibonaci数列:

$$ Fib(n) = \begin{cases} 1 &若 n=1或2 \\ Fib(n-1)+Fib(n-2) &其他 \\ \end{cases} $$

斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:$F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2)(n\ge 2,n \in N)$
  • 具有递归特性的数据结构

二叉树:

image-20220906144837664

广义表:

image-20220906144928279

  • 可递归求解的问题

迷宫问题:

走一步,就把下一步当成一个迷宫继续递归;

image-20220906145239744

Hanoi塔问题:

image-20220906145321471

分治法求解递归问题

分治法:对于一个较为复杂的问题,能够分解成几个相对简单的且解法相同或类

似的子问题来求解。

必备的三个条件:

  1. 能将一个问题转变成一个新问题,而新问题与原问题的解法相同或类同,不同的仅是处理的对象,且这些处理对象是变化有规律的
  2. 可以通过上述转化而使问题简化
  3. 必须有一个明确的递归出口,或称递归的边界

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

viod 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)依照被调用函数保存的返回地址将控制转移到调用函数

举例:求 n 的阶乘:

image-20220906153714461

可以看出,首先是递归调用,进行参数的传递,这个过程相当于压栈,然后将结果返回,回归求值,这个过程相当于出栈;这个称之为 ”递归工作站“

“递归工作栈”——递归程序运行期间使用的数据存储区。

“工作记录”——实在参数,周部变量,返回地址。

递归的优缺点

优点:结构清晰,程序易读

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

🧐 本文作者:
😉 本文链接:https://lukeyalvin.site/archives/96.html
😊 版权说明:本博客所有文章除特别声明外,均默认采用 CC BY-NC-SA 4.0 许可协议。
最后修改:2022 年 09 月 24 日
赏杯咖啡