第5章递归 >递归与递归程序设计 递归程序执行过程的分析 >递归程序到非递归程序的转换 递归程序设计的应用实例
第5章 递 归 ➢递归与递归程序设计 ➢递归程序到非递归程序的转换 ➢递归程序设计的应用实例 ➢递归程序执行过程的分析
51递归与递归程序设计 在一个函数的定义中出现了对自己本身的调用, 称之为直接递归;或者一个函数p的定义中包含了 对函数q的调用,而q的实现过程又调用了p,即函 数调用形成了一个环状调用链,这种方式称之为间接 递归。递归技术在算法和程序设计中是一种十分有 用的技术,许多高级程序设计语言均提供了支持递 归定义的机制和手段。 例1试编一个递归函数,求正整数n的阶乘值n 用 fact(n)表示n的阶乘值,据阶乘的数学定义可知: 1 n=0 fact(n) n*fact(n-1) n>0
5.1 递归与递归程序设计 在一个函数的定义中出现了对自己本身的调用， 称之为直接递归；或者一个函数p的定义中包含了 对函数q的调用，而q的实现过程又调用了p，即函 数调用形成了一个环状调用链, 这种方式称之为间接 递归。递归技术在算法和程序设计中是一种十分有 用的技术，许多高级程序设计语言均提供了支持递 归定义的机制和手段。 例1 试编一个递归函数，求正整数n的阶乘值n！。 用fact(n)表示n的阶乘值，据阶乘的数学定义可知： 1 n=0 fact(n) = n*fact(n-1) n>0
该问题的算法为: int fact(intn) i int if(==0)return(1); ese i m=n*Fact(n-1); return(m);) 例2试编一个递归函数,求第n项 Fibonaco级数的 值。 假设使用 Fiona(n)表示第n项 Fibonaco级数的值, 根据 Fibonacci级数的计算公式: n 1 Fibona(n)= 1 n=2 Fibona(n-1)+ Fibona(n-2) n>2
该问题的算法为： int Fact ( int n ) { int m; if (n= =0) return(1); else { m=n*Fact(n-1); return(m); } } 例2 试编一个递归函数，求第n项Fibonacci级数的 值。 假设使用Fibona(n)表示第n项Fibonacci级数的值， 根据Fibonacci级数的计算公式： 1 n=1 Fibona(n)= 1 n=2 Fibona(n-1)+ Fibona(n-2) n>2
该问题的算法为: int Fibona( int n Int m if (n==1) return(1) else if(n==2)return(1); else i m=Fibona(n-1)+ Fibona(n-2); return (m)
该问题的算法为： int Fibona ( int n ) { int m; if (n= =1) return (1); else if (n= =2) return(1); else { m=Fibona(n-1)+ Fibona(n-2); return (m); } }
递归程序设计具有以下两个特点: (1)具备递归出口。递归出口定义了递归的终止条 件,当程序的执行使它得到满足时,递归执行过程 便终止。有些问题的递归程序可能存在几个递归出 (2)在不满足递归出口的情况下,根据所求解问题 的性质,将原问题分解成若干子问题,这些子问题 的结构与原问题的结构相同,但规模较原问题小。 子问题的求解通过以一定的方式修改参数进行函数 自身调用加以实现,然后将子问题的解组合成原问 题的解。递归调用时,参数的修改最终必须保证递 归出口得以满足
递归程序设计具有以下两个特点： （1）具备递归出口。递归出口定义了递归的终止条 件，当程序的执行使它得到满足时，递归执行过程 便终止。有些问题的递归程序可能存在几个递归出 口； （2）在不满足递归出口的情况下，根据所求解问题 的性质，将原问题分解成若干子问题，这些子问题 的结构与原问题的结构相同，但规模较原问题小。 子问题的求解通过以一定的方式修改参数进行函数 自身调用加以实现，然后将子问题的解组合成原问 题的解。递归调用时，参数的修改最终必须保证递 归出口得以满足