递归经典习题

求n!

题目

设计求n!的递归算法

重点代码展示

int solve(int n) {
	if (n == 1) {
		return 1;
	}
	else return n * solve(n - 1);
}

求非空二叉链的结点之和

题目

分析二叉树的二叉链存储结构的递归性，设计求非空二叉链bt中所有结点值之和的递归算法，假设二叉链的data域为int型。

int sumtree(node* T) {
	if (T == NULL) return 0;
	else {
		return T->data + sumtree(T->rchild) + sumtree(T->lchild);
	}
}

先序序列和中序序列创建二叉树

题目

对于含n（n>0）个结点的二叉树，所有结点值为int类型，设计一个算法由其先序序列a和中序序列b创建对应的二叉链存储结构。

代码

BiTree createtree2(int a[], int b[], int n) {
	//a代表先序，b代表中序，n代表中序序列的第几号元素
	int i = 0;
	if (n <= 0) return NULL;//如果n为0则说明构建完毕
	BiTree t;
	if (!(t = (BiTree)malloc(sizeof(BiTree)))) exit(OVERFLOW);
	t->data = a[0];
	for (i = 0; i < n; i++) {
		if (a[0] == b[i]) break;
	}
	t->lchild = createtree2(a + 1, b, i);//递归左子树
	t->rchild = createtree2(a + i + 1, b + i + 1, n - i - 1);//递归右子树
	return t;
}

基于归纳思想的递归算法设计

题目

设计一个递归算法，输出一个大于零的十进制数n的各数字位，如n=123，输出各数字位为123。

代码 

void digits(int n)
{
	if (n != 0)
	{
		digits(n / 10);
		cout << n % 10;
	}
}