递归与分治策略课件.ppt

第2章 递归与分治策略Recursion ,divide and conquer method 学习要点:n 理解递归的概念。n 掌握设计有效算法的分治策略。n 通过下面的范例学习分治策略设计技巧。n （1）二分搜索技术；n （2）合并排序n （3）快速排序；n （4）最接近点对问题； 2.1 递归n 递归(recursion)是数学与计算机科学中的基本概念。直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。n 递归程序不能无限制地自我调用，否则就会永不终止，递归程序必须有终止条件。n 尽管递归程序在执行时间上往往比非递归程序要付出更多的代价，但有很多问题的数学模型