递归与广义表：定义、实现和应用——数据结构第5章复习要点。

本章主要讨论递归过程和广义表。递归算法是一种非常重要的算法设计思想，它通过将一个问题分解为更小的同类问题来求解，直到达到基本项可以直接求解。递归的定义可以用递归的过程来计算，递归的数据结构可以用递归的过程实现它的各种操作，递归问题也可以用递归的过程求解。因此，掌握递归算法的设计是非常重要的。 在设计递归算法时，首先需要考虑在什么条件下可以直接求解。如果可以直接求解，就设计基本项，即解决问题的最简单情况。如果不能直接求解，就考虑是否可以将问题缩小求解，设计归纳项，递归调用自身来解决规模更小的同类问题。通过多个递归过程的实例来理解递归是非常必要的。 然而，需要注意的是，递归过程在时间方面是低效的。因为每次递归调用都会创建新的递归栈帧，而且需要保存局部变量的值，当递归层数较大时，会占用大量的内存空间和时间。 除了递归算法，本章还介绍了广义表的概念。广义表是一种表，它的特点是允许表中套表，即表中的元素可以是其他表。因此，广义表不一定是线性结构，它可以是复杂的非线性结构，甚至允许递归。可以用多重链表来定义广义表。在讨论广义表时，特别需要注意递归在广义表操作实现中的应用。 在本章的复习中，首先要理解递归的概念，包括递归的定义、递归的数学表达形式和递归算法的基本形式。其次，需要理解递归算法的设计思想，即先考虑在什么条件下可以直接求解，然后设计基本项和归纳项。最后，需要通过多个递归过程的实例来加深对递归的理解。 综上所述，本章主要介绍了递归过程和广义表。递归算法是一种重要的算法设计思想，通过将一个问题分解为更小的同类问题来求解。递归的定义可以用递归的过程来计算，递归的数据结构可以用递归的过程实现它的各种操作，递归问题也可以用递归的过程求解。递归算法的设计需要考虑在什么条件下可以直接求解，设计基本项和归纳项。递归过程在时间方面是低效的。广义表是一种表，它的特点是允许表中套表，可以是复杂的非线性结构，甚至允许递归。在讨论广义表时，需要特别注意递归在广义表操作实现中的应用。在复习中，需要掌握递归的概念、递归算法的设计思想和多个递归过程的实例。