数据结构及算法分析(0)——引论

时间:2022-11-27 00:08:20

 

    引论提到算法递归的概念,递归在很多算法中都会出现。所谓递归,当一个函数用它自己来定义的时候就称为递归。

    递归调用有两大要素:

  • 基准情况。
  • 递归调用。

    并非所有的数学递归函数都能有效地由C语言的递归模拟来实现。一般来说,递归调用并非循环逻辑,它与其它的调用在处理上没什么不同,只是递归调用将反复进行直到基准情况出现。

    递归调用有四大基本法则:

  1. 基准情况。如先前提到,一个正确的递归必须具有不需要递归就能求解出的基准情况。一个没有基准情况的数学递归是没有意义的,也不能计算出正确的解,可能会陷入死循环甚至引起程序的崩溃。
  2. 不断推进。有了基准情况,递归调用还必须有一个正确的推进方向,递归调用必须朝着基准情况推进,否则也不能求解。
  3. 设计原则。假设所有的递归都有效。
  4. 合成效益法则。在求解一个问题的同一实例时,切勿在不同的递归调用中做重复的工作,这样会白白浪费资源。

另外,引论中提到很多的数学概念,这些其实不难,在大学的数学中都已经学过并且十分熟悉了。

 

习题

1.8  2100(mod 5)是多少?