C语言基础学习笔记（5）：递归

Guderian出品

把现成的代码拿来使用就称为复用，这么做可以大大提高编写效率。
C语言中的函数可以嵌套调用，不能嵌套定义。
定义.函数直接或间接调用了自己，称为递归调用（Recursive Call）。这样的函数，称为递归函数（Recursive Function）。
递归函数包含基本条件和一般条件。基本条件控制递归调用结束，一般条件控制递归调用项基本条件转化。如果没有基本条件或者一般条件不能转化为基本条件，此时递归无法结束，变成“无穷递归”。
通常下面三种情况需要使用递归：

（1）数学定义是递归的：计算阶乘，最大公约数和斐波那契数列

（2）数据结构时递归的：队列、链表、树和图

（3）问题的解法是递归的：汉诺塔，骑士游历，八皇后问题

典型递归问题示例：汉诺塔问题（题目链接）

先考虑比较简单的情形：当只有2个圆盘的时候如何解决？

将1号圆盘从A移到C
将2号圆盘从A移到B
将1号圆盘从C移到B

再考虑复杂的情形：当有n个圆盘的时候如何解决？使用数学归纳法，假设n-1个圆盘的汉诺塔问题已经解决，将“上面n-1个圆盘”看成一个整体：

将“上面n-1个圆盘”从A移到C
将第n号圆盘从A移到B
将“上面n-1个圆盘”从C移到B

#include <stdio.h>

void Hanoi(int n, char a, char b, char c);
void Move(int n, char a, char b);

int main()
{
	int n;
	printf("Input the number of disks:");
	scanf("%d", &n);
	printf("steps of moving %d disks form A to B by means of C:\n", n);
	Hanoi(n, 'A', 'B', 'C');
	return 0;
}

void Hanoi(int n, char a, char b, char c)
{
	if (n == 1)
	{
		Move(n, a, b);
	}
	else
	{
		Hanoi(n-1, a, c, b);	//将“上面n-1个圆盘”从A移到C
		Move(n, a, b);		   //将第n号圆盘从A移到B
		Hanoi(n-1, c, b, a);	//将“上面n-1个圆盘”从C移到B
	}
}

void Move(int n, char a, char b)
{
	printf("Move %d: from %c to %c\n", n, a, b);
}

【更多C语言系列】