文档介绍：数据结构与算法
-
递归
递归的概念
递归的定义若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的;若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。
在以下三种情况下,常常用到递归方法。
定义是递归的
数据结构是递归的
问题的解法是递归的
定义是递归的
求解阶乘函数的递归算法
long Factorial ( long n ) {
if ( n == 0 ) return 1;
else return n*Factorial (n-1);
}
例如,阶乘函数
求解阶乘 n! 的过程
计算斐波那契数列的函数Fib(n)的定义
求解斐波那契数列的递归算法
long Fib ( long n ) { if ( n <= 1 ) return n; else return Fib (n-1) + Fib (n-2);
}
数据结构是递归的
搜索链表最后一个结点并打印其数值
template <class Type>
void Find ( ListNode<Type> *f ) {
if ( f →link == NULL )
cout << f →data << endl;
else Find ( f →link );
}
例:单链表结构
在链表中寻找等于给定值的结点 并打印其数值 template <class Type> void Print ( ListNode<Type> *f ) { if ( f != NULL) if ( f →data == x ) cout << f→data << endl; else Print ( f→link ); }
问题的解法是递归的
例: 汉诺塔(Tower of Hanoi)问题
#include <>
#include "”
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 ); }
}