西南科技大学：《数据结构》课程教学资源（PPT课件讲稿）第六章 递归

递归的概念 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

数据结构是递归的 例如,单链表结构 f 搜索链表最后一个结点并打印其数值 template void Find( ListNode p if(p→next==NULL) cout<<p→data<<endl; else find(p→next);

数据结构是递归的 搜索链表最后一个结点并打印其数值 template void Find ( ListNode *p) { if ( p →next == NULL ) cout << p →data << endl; else Find ( p→next ); } 例如，单链表结构

在链表中寻找等于给定值的结点 并打印其数值 template void Print( ListNode P if(pl=NULL) if(p→data==x) cout<<p→data<<endl; else print(p→next)

在链表中寻找等于给定值的结点 并打印其数值 template void Print ( ListNode *p) { if ( p!= NULL) if ( p →data == x ) cout << p→data << endl; else Print ( p→next ); }

递归算法的设计 DS 计设计思想:分而治之 算机学院信息教研室 原问题 子问题 设计递归出口 最终可直接求解

递归算法的设计 设计思想：分而治之 原问题 子问题 最终可直接求解 计 算 机 学 院 信 息 教 研 室 DS 设计递归出口

问题的解法是递归的 例如,汉诺塔( Tower of hanoi)问题 B

问题的解法是递归的 例如，汉诺塔(Tower of Hanoi)问题

汉诺塔问题

汉诺塔问题 A B C