当前位置：首页 > news >正文

数据结构与算法--递归

news 来源：原创 2024/9/20 11:35:44

文章目录

- 回顾
- 提要
- 1.递归的定义
- - 1.1 何时使用递归
  - 1.2 定义使用递归
  - - 阶乘公式的定义
    - 斐波那契数列的定义
  - 1.3 递归数据结构的应用
  - - 单链表结构
    - 查找链表最后一个结点并打印其数值
    - 在链表中查找等于给定值的结点并打印其数值
    - 求一个不带头结点的单链表值域之和
- 2.递归的执行过程
- 3.递归的实现
- - 3.1 直接递归与间接递归示例
  - 3.2 递归工作栈
- 4.递归的设计方法
- - 4.1 示例：汉诺塔问题的算法实现
  - 4.2递归算法的基本特性
- 5.递归算法到非递归算法的转换
- - 5.1 递归算法与非递归算法的对比
  - 5.2 递归算法的选择建议
- 6.总结

回顾

栈：后进先出 (LIFO)
队列：先进先出 (FIFO)
链队列的4要素
- 循环队列的下标运算：( (X+1) % Max )
- 队空条件：( front == rear )
- 队满条件：( (rear + 1) % MaxSize == front )
- 队列长度：( (rear - front + MaxSize) % MaxSize )

提要

递归的定义
递归的执行过程
递归的实现
递归的设计方法
递归算法到非递归算法的转换

1.递归的定义

直接递归：函数直接调用自己
间接递归：函数间接调用自己
尾递归：求n!(n为正整数)的递归函数。
函数fac(n) 直接调用fac(n-1)自身，是直接递归。
递归调用是最后一条语句，又属于尾递归。

1.1 何时使用递归

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

定义使用递归：许多数学公式、数列等的定义是递归的。
数据结构中使用递归：某些数据结构天然支持递归操作。
问题的解法使用递归：某些问题的解法本质上是递归的。

1.2 定义使用递归

阶乘公式的定义

阶乘公式是一个典型的递归定义的例子，其递归关系可以表示为：

( n! = n \times (n-1)! ) 当 ( n > 1 )
( 1! = 1 )

斐波那契数列的定义

斐波那契数列也是一个递归定义的例子，其递归关系为：

( F(n) = F(n-1) + F(n-2) ) 当 ( n > 1 )
( F(0) = 0 )
( F(1) = 1 )

以下是斐波那契数列的递归实现代码：

int Fib(int n) {if (n <= 1) return n;else return Fib(n - 1) + Fib(n - 2);
}

1.3 递归数据结构的应用

单链表结构

单链表是一种递归数据结构，因为它的每个元素都包含指向下一个元素的指针。
在这里插入图片描述

在这里插入图片描述

查找链表最后一个结点并打印其数值

对于递归数据结构，采用递归的方法编写算法既方便又有效。
以下是使用递归在单链表中查找最后一个结点的代码示例：

void Find(LinkNode *p) {if (p->next == NULL) {std::cout << p->data << std::endl;} else {Find(p->next);}
}

在链表中查找等于给定值的结点并打印其数值

以下是使用递归在单链表中查找等于给定值的结点的代码示例：
在这里插入图片描述

void FindItem(LinkNode *p, ElemType x) {if (p != NULL) {if (p->data == x) std::cout << p->data << std::endl;else FindItem(p->next, x);}
}

求一个不带头结点的单链表值域之和

以下是使用递归求单链表值域之和的代码示例：
在这里插入图片描述

int Sum(LinkNode *p) {if (p == NULL) return 0;else return p->data + Sum(p->next);
}

2.递归的执行过程

递归模型：反映递归问题的递归结构
- 递归模型是递归算法的抽象，反映一个递归问题的递归结构。
- 例如, 阶乘递归算法对应的递归模型如下：
- fun(1)=1 n=1 (1)
- fun(n)=n*fun(n-1) n>1 (2)
- 第一个式子是递归的终止条件，称为递归出口。
- 第二个式子是fun(n)的值与fun(n-1)的值之间的关系，称为递归体。
递归出口：终止条件
递归体：大问题与小问题的关系
递归模型是由递归出口和递归体两部分组成。
- 递归体表示“大问题”与**“小问题”**的关系。
- 递归出口为“最小问题”，可以直接求得结果。
递归的执行过程由分解和求值两部分构成：
- （1）分解是指把“最大问题”逐步分解为“小问题”直至“最小问题”；
- （2）求值是指根据求得的“最小问题”的值重新代入递归体，最终得到“最大问题”的值。

3.递归的实现

递归函数的运行过程类似于多个函数的嵌套调用，差别仅在于“调用函数和被调用函数是同一个函数”。
递归调用在内部实现时并不是把每次调用所需的代码都放入内存，而是采取代码共享的方式。
系统为每次调用开辟一组存储单元，用来存放本次调用的相关数据。

3.1 直接递归与间接递归示例

// 直接递归示例：计算阶乘
int fac(int n) {if (n == 0 || n == 1) return 1;else return n * fac(n - 1);
}// 间接递归示例：斐波那契数列
int Fib(int n) {if (n <= 1) return n;else return Fib(n - 1) + Fib(n - 2);
}

3.2 递归工作栈

为了保证“每一层的递归调用”都是对“本层”的数据进行操作，在执行递归函数的过程中需要一个“递归工作栈”。它的作用是:
将递归调用时的实参和函数返回地址传递给下一层执行的递归函数；
保存本层的参数和局部变量，以便从下一层返回时重新使用它们。

4.递归的设计方法

递归函数的一般设计格式
- 递归出口：满足条件直接返回
- 递归项：返回较小问题的递归调用

4.1 示例：汉诺塔问题的算法实现

任务：将塔座A上的圆盘移动到塔座C上。
移动规则：1. 每次移动一个圆盘；
2. 圆盘只能在塔座A，B，C之间移动;
3. 大圆盘不能放在小圆盘上。
4.

void Hanoi(int n, char X, char Y, char Z) {if (n == 1) {std::cout << X << "->";std::cout << Z << "\t";} else {Hanoi(n - 1, X, Z, Y);std::cout << X << "->";std::cout << Z << "\t";Hanoi(n - 1, Y, X, Z);}
}