递归

基本概念

1. 函数体内直接调用自己：直接递归
2. 函数通过调用其他函数，反过来调用自己：间接递归
3. 任意循环都能写成递归

递归程序的阅读

1. 根据调用的情况，将函数作为图中的节点，使用有向边进行连接
2. 从递归的出口点开始，逐次返回，在边上使用返回值作为边的权重

递归的三要素

• 写递归代码时，通过以下三个要素来写（以下使用二叉树的先序遍历为例）
• 确定递归函数的参数和返回值
  • void preorder(BiNode<T>* node)

    通过对问题的具体分析，我们还可以写出尾递归来提高递归的效率

• 确定终止条件
  • if(node == NULL) return;
• 确定每层递归的逻辑 C++ visit(node); preorder(node->lchild); preorder(node->rchild);

优缺点

优点

1. 容易编程实现
2. 健壮性和可维护性好
3. 充分利用计算机的算力
4. 代码简短，便于阅读

缺点

• 时空效率低