第五章递归与广义表 递归的概念 递归过程与递归工作栈 递归与回溯 广义表
◼ 递归的概念 ◼ 递归过程与递归工作栈 ◼ 递归与回溯 ◼ 广义表
递归的概念 递归的定义若一个对象部分地包含它 自己,或用它自己给自己定义,则称这 个对象是递归的;若一个过程直接地或 间接地调用自己则称这个过程是递归 的过程。 以下三种情况常常用到递归方法。 定义是递归的 数据结构是递归的 问题的解法是递归的
递归的概念 ◼ 递归的定义 若一个对象部分地包含它 自己, 或用它自己给自己定义, 则称这 个对象是递归的；若一个过程直接地或 间接地调用自己, 则称这个过程是递归 的过程。 ◼ 以下三种情况常常用到递归方法。 ◼ 定义是递归的 ◼ 数据结构是递归的 ◼ 问题的解法是递归的
定义是递归的 例如,阶乘函数 当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