【408数据结构与算法】—栈与递归（十二）

【408数据结构与算法】—栈与递归（十二）

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

例如：递归求n的阶乘

#include <stdio.h>
int jiecheng(int n)
{
  if (n == 1)
    return 1;
  else
    return n*jiecheng(n - 1);
}
int main()
{
  int n = 0;
  int a = 0;
  scanf("%d", &n);
  a=jiecheng(n);
  printf("%d的阶乘%d\n", n , a);
  return 0;
}

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

1️⃣递归定义的数学函数

阶乘函数

斐波那契数列

2️⃣具有递归特性的数据结构

3️⃣可递归求解的问题

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

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

📢使用分治法具备的三个条件

• 能将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，且这些处理的对象是变化有规律的
• 可以通过上述转化而使问题简化

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

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

• List item

函数调用过程

调用前，系统完成：

• 将实参、返回地址等传递给被调用函数
• 为被调用函数的局部变量分配存储区

• 将控制转移到被调用函数的入口

调用后，系统完成：

• 保存被调用函数的计算结果
• 释放被调用函数的数据区

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

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

求解n! 的过程

递归的优缺点：

• 优点：结构清晰，程序容易读
• 缺点：每次调用要生成工作记录，保存状态信息，入栈，返回时要出栈，恢复状态信息，时间开销大。

方法一：单向递归，循坏结构

虽然有一处以上的递归调用语句，但各次递归调用语句的参数只和主调函数有关，相互之间参数无关，并且这些递归调用语句处于算法的最后。

三、借助栈改写递归

借助栈改写递归的方法（了解）

• 递归程序在执行时需要系统提供栈来实现
• 仿照递归算法执行过程中递归工作栈的状态可写出相应的非递归程序
• 改写后的非递归算法与原来的递归算法相比，结构不够清晰，可读性较差，有的还需要一系列优化