递归

概念

函数直接或间接地调用自身

递归与分治

  • 分治法
    • 问题的分解
    • 问题规模的分解
  • 折半查找（递归）
  • 归并查找（递归）
  • 快速排序（递归）

递归与迭代

  • 迭代：反复利用变量旧值推出新值
  • 折半查找（迭代）
  • 归并查找（迭代）

广义表

头尾链表存储表示

广义表的头尾链表存储表示和图片

  1. // 广义表的头尾链表存储表示
  2. typedef enum {ATOM, LIST} ElemTag;
  3. // ATOM==0：原子，LIST==1：子表
  4. typedef struct GLNode {
  5.     ElemTag tag;
  6.     // 公共部分，用于区分原子结点和表结点
  7.     union {
  8.         // 原子结点和表结点的联合部分
  9.         AtomType atom;
  10.         // atom 是原子结点的值域，AtomType 由用户定义
  11.         struct {
  12.             struct GLNode *hp, *tp;
  13.         } ptr;
  14.         // ptr 是表结点的指针域，prt.hp 和 ptr.tp 分别指向表头和表尾
  15.     } a;
  16. } *GList, GLNode;

递归 - 图1

扩展线性链表存储表示

扩展线性链表存储表示和图片

  1. // 广义表的扩展线性链表存储表示
  2. typedef enum {ATOM, LIST} ElemTag;
  3. // ATOM==0：原子，LIST==1：子表
  4. typedef struct GLNode1 {
  5.     ElemTag tag;
  6.     // 公共部分，用于区分原子结点和表结点
  7.     union {
  8.         // 原子结点和表结点的联合部分
  9.         AtomType atom; // 原子结点的值域
  10.         struct GLNode1 *hp; // 表结点的表头指针
  11.     } a;
  12.     struct GLNode1 *tp;
  13.     // 相当于线性链表的 next，指向下一个元素结点
  14. } *GList1, GLNode1;

递归 - 图2