一、递归的概念
是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现象。
在计算机编程里，递归指的是一个过程：函数不断引用自身，直到引用的对象已知。
通俗的说就是函数体自己调用自己的情况，叫做递归。
递归在一定情况下可以快速解决很多问题，让代码更加简洁。实际上所有的递归算法都可以转化为和它等价的非递归算法。
二、常见的递归问题
1、Fibonacci数列
设An是一个数列，当n<=2时，An=1；当n>2时，满足等式An = An-1+An-2，也就是说当n大于2时，每一项都等于前两项的和。这样的数列称为Fibonacci数列，也成为“兔子数列”。
如何在c语言中求Fibonacci数列的每一项呢？
可以定义一个函数Fibo，输入一个正整数n作为参数，由函数满足的等式Fibo（n）=Fibo（n-1）+Fibo（n-2），不难发现函数体自己调用了自己，所以它是一个递归问题。
上述等式只有在n>2时满足，当n<=2时应该让函数返回值1。具体的代码实现如下——
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
//用递归的方式求斐波那契数
fibo_num(unsigned int n)
{
if (n <= 2)
return 1;
else
return fibo_num(n - 1) + fibo_num(n - 2);
}
int main()
{
unsigned int n = 0;
scanf("%d", &n);
int ret = fibo_num(n);
printf("%d", ret);
return 0;
}刚刚说过，任何的递归算法都可以转化为和它等价的非递归算法。
Fibonacci数列的非递归算法思路：定义三个整形值a，b，c。（c代表数列的第n项，a和b分别是c的前两项）
当n>2时候，c = b+a，而前两项b和a也要分别往前算它们的前两项，所以每次加的时候都要把c赋给b，b赋给a，放入一个循环体中，每次循环都让循环变量n减1。具体代码实现如下——
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
//用递归的方式求斐波那契数
fibo_num(unsigned int n)
{
if (n <= 2)
return 1;
else
return fibo_num(n - 1) + fibo_num(n - 2);
}
int main()
{
unsigned int n = 0;
scanf("%d", &n);
int ret = fibo_num(n);
printf("%d", ret);
return 0;
}2、汉诺塔问题
有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动，设移动次数为H(n)。
n为1时 Hn= 1，n为2时Hn= 3，n为3时Hn=7.。。。。。。
则H(n)满足的关系式子为，H(n)=2*H（n-1）+1（n>2)
代码实现如下——
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
num(unsigned int n)
{
if (n == 1)
return 1;
if (n > 1)
return 2*num(n - 1) + 1;
}
int main()
{
unsigned int n = 0;
scanf("%d", &n);
int ret = num(n);
printf("%d", ret);
return 0;
}当然它也有等价的非递归代码——
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
num(unsigned int n)
{
int a = 1;
int c = 0;
if (n == 1)
return 1;
while (n > 1)
{
c = 2 * a + 1;
a = c;
n--;
}
return c;
}
int main()
{
unsigned int n = 0;
scanf("%d", &n);
int ret = num(n);
printf("%d", ret);
return 0;
}