递归的概念 DS ◆递归的定义若一个对象部分地包含它 计自己,或用它自已给自己定义,则称这个 算对象是递归的;若一个算法直接地或间 机接地调用自己,则称这个算法是递归的算 法。 ◆在以下三种情况下,常常用到递归方法 自 定义是递归的 教研室 数据结构是递归的 问题的解法是递归的
递归的概念 递归的定义 若一个对象部分地包含它 自己, 或用它自己给自己定义, 则称这个 对象是递归的；若一个算法直接地或间 接地调用自己, 则称这个算法是递归的算 法。 在以下三种情况下，常常用到递归方法。 ◼ 定义是递归的 ◼ 数据结构是递归的 ◼ 问题的解法是递归的 计 算 机 学 院 信 息 教 研 室 DS
递归函数的定义 DS 个算法可以分解成 计算机学院 若干相同的小算法 分解到某简单的子算法时终止 信◆有一个或几个终止条件 自 递归:由其前面的值求当前值 教研室 递归必须导致终止条件
计 算 机 学 院 信 息 教 研 室 DS 递归函数的定义 一个算法可以分解成 若干相同的小算法 分解到某简单的子算法时终止 有一个或几个终止条件 递归：由其前面的值求当前值 递归必须导致终止条件
定义是递归的 例如,阶乘函数 当n=0时 n*(n-1)!,当n≥1时 求解阶乘函数的递归犷法 long Factorial (long n) if(n==0)return 1; else return n* Factorial(n-1)
定义是递归的 求解阶乘函数的递归算法 long Factorial ( long n ) { if ( n == 0 ) return 1; else return n*Factorial (n-1); } 例如，阶乘函数 − = = 当 时 当 时 ( 1)!, 1 1, 0 ! n n n n n
解阶乘n的 参数 计算 返回 0 0!=I 0 参数 计算 返回 1*Factorial(o) 1返 参数传递 参数 计算 返回 2 2*Factorial(1) 2 参数 计算 返 3 Factorial (2) 6 6值 参数 计算 返回 壬* Factorial(39) 24 24 主程序main
求解阶乘 n! 的过程
计算斐波那契数列的函数Fib(n)的定义 n=0.1 Fib(n) Fib(n-1)+Fib(n-2), n>1 求解斐波那契数列的递归η法 long Fib(long n)& if (n<=1 return n else return Fib (n-1)+ Fib(n-2);
计算斐波那契数列的函数Fib(n)的定义 求解斐波那契数列的递归算法 long Fib ( long n ) { if ( n <= 1 ) return n; else return Fib (n-1) + Fib (n-2); } − + − = = ( 1) ( 2), 1 , 0,1 ( ) Fib n Fib n n n n Fib n