第沉章递归 递归( Recurve)的概念 迷宫(Maze问题 递归过程与递归工作栈 广义表( General lists)
递归(Recurve)的概念 迷宫(Maze)问题 递归过程与递归工作栈 广义表 (General Lists )
递归的概念 递归的定义若一个对象部分地包含它自 己,或用它自己给自己定义,则称这个对象 是递归的;若一个过程直接地或间接地调 用自己,则称这个过程是递归的过程 在以下三种情况下,常常用到递归方法。 定义是递归的 数据结构是递归的 问题的解法是递归的
递归的概念 递归的定义 若一个对象部分地包含它自 己, 或用它自己给自己定义, 则称这个对象 是递归的；若一个过程直接地或间接地调 用自己, 则称这个过程是递归的过程。 在以下三种情况下，常常用到递归方法。 定义是递归的 数据结构是递归的 问题的解法是递归的
定义是递的 例如,阶乘函数 当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 递3 6值 参数 计算 返回 壬* Factorial(39) 24 24 主程序main
求解阶乘 n! 的过程
计算斐波那契数列的函数Fib(m)的定义 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