探讨的问题一 递归函数的语义 对应的整数域上的数学函数的定义(x≥0〉 -f(x)=ifx=0 then 1 else xx fx-1) g(x)=ifx=0 then 1 else (if x =1 then g(3)else g(x-2)) 换一个角度：把两式看成是关于和？的函数方程 阶乘函数是第一个方程的解 把f用函数{0,1)，1,1)，(2,2)，3,6)，.}代入等 式的两边，等式两边的函数相同 因为对任意自然数n,等式两边的函数作用于n的 结果相等
探讨的问题——递归函数的语义 • 对应的整数域上的数学函数的定义（x 0） – f(x) = if x = 0 then 1 else x f(x−1) – g(x) = if x = 0 then 1 else (if x =1 then g(3) else g(x−2)) 换一个角度：把两式看成是关于f 和g的函数方程 – 阶乘函数是第一个方程的解 把f 用函数{ 0, 1, 1, 1, 2, 2, 3, 6, … }代入等 式的两边，等式两边的函数相同 因为对任意自然数n，等式两边的函数作用于n的 结果相等 12
探讨的问题一 递归函数的语义 对应的整数域上的数学函数的定义(x≥0》 -f(x)=ifx=0 then 1 else xx fx-1) g(x)=ifx=0 then 1 else (if x =1 then g(3)else g(x-2)) 换一个角度：把两式看成是关于f和？的函数方程 一阶乘函数是第一个方程的解 第二个方程有无数个解（a可取任意自然数) x是偶数 x是奇数 即{0,1,1，a〉，(2,1)，3，a),(4,1,5,a),…
探讨的问题——递归函数的语义 • 对应的整数域上的数学函数的定义（x 0） – f(x) = if x = 0 then 1 else x f(x−1) – g(x) = if x = 0 then 1 else (if x =1 then g(3) else g(x−2)) 换一个角度：把两式看成是关于f 和g的函数方程 – 阶乘函数是第一个方程的解 – 第二个方程有无数个解（a可取任意自然数） 1, x是偶数 h(x) = a, x是奇数 即{ 0, 1, 1, a , 2, 1, 3, a , 4, 1, 5, a, … }13
探讨的问题一 递归函数的语义 对应的整数域上的数学函数的定义(x≥0》 -f(x)=ifx=0 then 1 else xx f(x-1) g(x)=ifx=0 then 1 else (if x =1 then g(3)else g(x-2)) 换一个角度：把两式看成是关于f和g的函数方程 一阶乘函数是第一个方程的解 若偏函数可采用，则第二个方程还有一个解 x是偶数 h() 没有定义 x是奇数 即{0,1〉，2,1〉，〈4,1)，〈6,1)，…
探讨的问题——递归函数的语义 • 对应的整数域上的数学函数的定义（x 0） – f(x) = if x = 0 then 1 else x f(x−1) – g(x) = if x = 0 then 1 else (if x =1 then g(3) else g(x−2)) 换一个角度：把两式看成是关于f 和g的函数方程 – 阶乘函数是第一个方程的解 – 若偏函数可采用，则第二个方程还有一个解 1, x是偶数 h(x) = 没有定义, x是奇数 即{ 0, 1, 2, 1, 4, 1, 6, 1, … } 14
探对的问题一 递归函数的语义 对应的整数域上的数学函数的定义(x≥0》 -f(x)=ifx=0 then 1 else xx fx-1) g(x)=ifx=0 then 1 else (ifx =1 then g(3)else g(x-2)) 换一个角度：把两式看成是关于f和g的函数方程 问题： -怎样求解这样的函数方程？ 若函数方程有多个解，哪个解为我们所需？该解 和其它解之间的关系怎么用数学语言进行描述？ 这是下面要解决事情
探讨的问题——递归函数的语义 • 对应的整数域上的数学函数的定义（x 0） – f(x) = if x = 0 then 1 else x f(x−1) – g(x) = if x = 0 then 1 else (if x =1 then g(3) else g(x−2)) 换一个角度：把两式看成是关于f 和g的函数方程 问题： – 怎样求解这样的函数方程？ – 若函数方程有多个解，哪个解为我们所需？该解 和其它解之间的关系怎么用数学语言进行描述？ – 这是下面要解决事情 15
探讨的问题一 递归函数的语义 需要把有关函数的知识扩宽，才能继续讨论 函数的定义域和值域从数值集合扩大到包括非数 值集合和函数集合，并给出单调函数和连续函数 的更一般定义 -从一阶函数扩大到包括高阶函数 高阶函数：D1×·×Dn→D,在D1,Dn和D 中，至少有一个是函数类型 -方程的概念从数值方程扩展到函数方程 例：fx)=ifx=0then1 else x×fx-l) -了解函数不动点概念
探讨的问题——递归函数的语义 • 需要把有关函数的知识扩宽，才能继续讨论 – 函数的定义域和值域从数值集合扩大到包括非数 值集合和函数集合，并给出单调函数和连续函数 的更一般定义 – 从一阶函数扩大到包括高阶函数 高阶函数：D1 … Dn→ D，在D1 , …, Dn和D 中，至少有一个是函数类型 – 方程的概念从数值方程扩展到函数方程 例：f(x) = if x = 0 then 1 else x f(x−1) – 了解函数不动点概念 16