清华大学：《C++数据结构》第五章 递归与广义表

第五章递归与广义表 递归的概念 递归过程与递归工作栈 递归与回溯 广义表

◼ 递归的概念 ◼ 递归过程与递归工作栈 ◼ 递归与回溯 ◼ 广义表

递归的概念 递归的定义若一个对象部分地包含它 自己,或用它自己给自己定义,则称这 个对象是递归的;若一个过程直接地或 间接地调用自己则称这个过程是递归 的过程。 以下三种情况常常用到递归方法。 定义是递归的 数据结构是递归的 问题的解法是递归的

递归的概念 ◼ 递归的定义 若一个对象部分地包含它 自己, 或用它自己给自己定义, 则称这 个对象是递归的；若一个过程直接地或 间接地调用自己, 则称这个过程是递归 的过程。 ◼ 以下三种情况常常用到递归方法。 ◼ 定义是递归的 ◼ 数据结构是递归的 ◼ 问题的解法是递归的

定义是递归的 例如,阶乘函数 当n=0时 n*(n-1)!,当n≥1时 求解阶乘函数的递归算法 long Factorial long n)t if (n==0)return I 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!的过程 主程序main:fact(4) 参数4计算4*fact(3)返回24 递参 结回 归数二参数3计算3+f2)返回6果归 调传 返求 用递参数2计算2c(1)返回2回值 参数1计算1*ac0)返回1 参数0直接定值=1返回1

求解阶乘 n! 的过程 主程序 main : fact(4) 参数 4 计算 4*fact(3) 返回 24 参数 3 计算 3*fact(2) 返回 6 参数 2 计算 2*fact(1) 返回 2 参数 1 计算 1*fact(0) 返回 1 参数 0 直接定值 = 1 返回 1 参 数 传 递 结 果 返 回 递 归 调 用 回 归 求 值

数据结构是递归的 例如,单链表结构 ff 个结点,它的指针域为NULL,是 一个单链表; 个结点,它的指针域指向单链表, 仍是一个单链表

数据结构是递归的 ◼ 一个结点，它的指针域为NULL，是 一个单链表; ◼ 一个结点，它的指针域指向单链表， 仍是一个单链表。 例如，单链表结构 f  f 

搜索链表最后一个结点并打印其数值 template void Print( ListNode*)i if(f->ink=- NULL cout data link ) 递归找链尾 Lao+a+a3+an

搜索链表最后一个结点并打印其数值 template void Print ( ListNode *f ) { if ( f ->link == NULL ) cout data link ); } f f f f f a0 a1 a2 a3 a4  递归找链尾

在链表中寻找等于给定值的结点并打印 其数值 template void Print( ListNode*f, Type&x)t if(f= NULL if (f-> data ==X cout data link, x); 递归找含值的结点 f-十xA f f

在链表中寻找等于给定值的结点并打印 其数值 template void Print ( ListNode *f, Type& x ) { if ( f != NULL ) if ( f -> data == x ) cout data link, x ); } f f f f  递归找含x值的结点 x

问题的解法是递归的 例如,汉诺塔( Tower of hanoi)问题的解法: 如果n=1,则将这一个盘子直接从A柱 移到C柱上。否则,执行以下三步: ①用C柱做过渡,将A柱上的(n-1)个 盘子移到B柱上: ②将A柱上最后一个盘子直接移到C柱 上 ③用A柱做过渡,将B柱上的(m-1)个 盘子移到C柱上

问题的解法是递归的 例如，汉诺塔(Tower of Hanoi)问题的解法： 如果 n = 1，则将这一个盘子直接从 A 柱 移到 C 柱上。否则，执行以下三步： ① 用 C 柱做过渡，将 A 柱上的 (n-1) 个 盘子移到 B 柱上： ② 将 A 柱上最后一个盘子直接移到 C 柱 上； ③ 用 A 柱做过渡，将 B 柱上的 (n-1) 个 盘子移到 C 柱上

A B A B A B B

#include #include strclass. h void Hanoi (int n, String A, String B, String C)i /解决汉诺塔问题的算法 if(n-1) cout<<move<<a<<to <<C<< endl else( Hanoi(n-1,A, C,B); cout << move <<a<< to <<c << endl Hanoi(n-1,B,A,C);

#include #include "strclass.h” void Hanoi (int n, String A, String B, String C) { //解决汉诺塔问题的算法 if ( n == 1 ) cout << " move " << A << " to " << C << endl; else { Hanoi ( n-1, A, C, B ); cout << " move " << A << " to " << C << endl; Hanoi ( n-1, B, A, C ); } }