概念

简单点说，递归就是函数自己调用自己。

1
2
3
4
5
函数A()
{
    ……
    函数A()
}

递归的思想

递归中的递就是递推的意思，归就是回归。

递归的思想就是把大事化小的思想。

递归的限制条件

  • 递归存在限制条件，当满足这个限制条件后，递归不再继续。

  • 每次调用递归后会越来越接近这个限制条件。

示例

求 n 的阶乘

1
2
3
4
5
6
7
8
    int Fact_Nor(int n)
{
	// 采用循环方式实现阶乘
	int i, s = 1;
	for (i = 1; i <= n; i++)
		s *= i;
	return s;
}
1
2
3
4
5
6
7
8
9
10
11
12
int Fact_Rec(int n)
{
	// 采用递归方式实现阶乘
	if (n == 1)
	{
		return 1;
	}
	else
	{
		return n * Fact_Rec(n - 1);
	}
}
1
2
3
4
5
int n;
printf("请输入一个整数：");
scanf("%d", &n);
printf("阶乘（非递归方式）=%d\n", Fact_Nor(n));
printf("阶乘（递归方式）=%d\n", Fact_Rec(n));


逆序打印一个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Print_Rev_Nor(int n)
{
	// 采用循环方式实现逆序打印
    while (n)
    {
		printf("%d ", n % 10);
		n /= 10;
    }
}

void Print_Rev_Rec(int n)
{
	// 采用递归方式实现逆序打印
	// 是个位数就直接打印，否则先递归调用打印高位，再打印个位
    if (n > 9)
    {
		Print_Rev_Rec(n / 10);
    }
    printf("%d", n % 10);
}
1
2
3
4
5
int num = 0;
scanf("%d", &num);
Print_Rev_Rec(num);
printf("\n");
Print_Rev_Nor(num);


求第 n 个斐波那契数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int Fib_Rec(int n)
{
	// 采用递归方式计算第 n 项斐波那契数
    if (n == 1 || n == 2)
    {
        return 1;
    }
	return Fib_Rec(n - 1) + Fib_Rec(n - 2);
}

int Fib_Nor(int n)
{
	// 采用循环方式计算第 n 项斐波那契数
    int a = 1;
    int b = 1;
    int c = 0;
	for (int i = 3; i <= n; i++)
	{
		c = a + b;
		a = b;
		b = c;
	}
	return c;
}
1
2
3
4
int n;
scanf("%d", &n);
printf("斐波那契数（非递归方式）= %d\n", Fib_Nor(n));
printf("斐波那契数（递归方式）= %d\n", Fib_Rec(n));

递归与迭代

对于前文中的 Fact_Nor 与 Fact_Rec 都能够实现阶乘的作用。

实际上 Fact_Nor 的效率更高。

事实上，诸多问题是以递归的方式解释的，但在用代码解决时使用迭代的方法更多。

当一个问题难以用迭代的方式实现时，递归的简洁性就可以补偿他带来的额外写

的性能开销。

至于为什么递归函数在性能开销上会更大，会在另一篇文章中进行详细解释。