在现实当中，我们只有在迫不得已的情况下才使用递归，因为递归本身的效率并不理想，但他的思想却值得我们留存在记忆之中。
使用递归实现上述问题
int Fib(int i)
{
if(i < 2)
return i == 0 ? 0 : 1;
return Fib(i-1)+ Fib(i-2);
}
每个递归定义必须至少有一个条件，当满足这个条件时递归不再进行，即函数不再调用自身而是返回。
例题一：写一个函数，输入n，求斐波那契数列的第n项。
//第一要素：明确你这个函数想要干什么
//函数功能：计算斐波那契数列的第n项
long long Fibonacci(unsigned int n)
{
//第二要素：寻找递归结束条件
if( n <= 1)
return i == 0 ? 0 : 1;
//第三要素：找出函数的等价关系式
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
上面的递归实现效率太低，原因在于我们在求斐波那契数列第n项的时候，中间计算了很多重复项，而且是不必要的计算，如下图的递归树：
改进的方法：使用迭代
long long Fibonacci(unsigned int n)
{
int result[2] = {0,1};
if(n < 2)
return result[n];
long long fibNumOne = 1;
long long fibNumTwo = 0;
long long fibN = 0;
for(int i = 2; i <= n; i++)
{
fibN = fibNumOne + fibNumTwo;
fibNumTwo = fibNumOne;
fibNumOne = fibN; //移动位置
}
return fibN;
}
例题二：写一个函数，输入n，求n的阶乘n!。
//第一要素：明确你这个函数想要干什么
//函数功能：计算n的阶乘
long long f(unsigned int n)
{
//第二要素：寻找递归的结束条件
if(n <= 2)
return n;
//第三要素：找出函数的等价关系式
return n * f(n-1);
}
例题三：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
//第一要素：明确你这个函数想要干什么
//函数功能：计算青蛙跳上一个n级的台阶总共有多少种跳法
long long jump(unsigned int n)
{
//第二要素：寻找递归结束条件
if( n <= 2)
return n;
//第三要素：找出函数的等价关系式
return jump(n - 1) + jump(n - 2);
}
例题四：编写一个递归函数，实现将输入的任意长度的字符串反向输出的功能。
//第一要素：明确你这个函数想要干什么
//函数功能：将输入的任意长度的字符串反向输出
void print()
{
char a;
scanf("%c", &a);
//第三要素：找出函数的等价关系式
if( a != '#') print();
//第二要素：寻找递归结束条件，#表示递归结束，进行返回输出。
if( a != '#') printf( "%c", a);
}
折半查找法是一种常用的查找方法，该方法通过不断缩小一半的查找范围，直到达到目的，所以效率比较高。
线性检索和二分检索求 1 的位置：
线性检索和二分检索求 23 的位置：
例题背景：一位法国数学家曾编写过一个印度的古老传说：在世界中心贝纳勒斯的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由小到大的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。将X的盘子移到Z上
这其实也是一个经典的递归问题。我们可以做这样的考虑：
例题五：编程实现汉诺塔的移动过程
#include <stdio.h>
//第一要素：明确你这个函数想要干什么
// 函数功能：将 n 个盘子从 x 借助 y 移动到 z
void move(int n, char x, char y, char z)
{
//第二要素：寻找递归结束条件，当n=1时，直接将盘子从x移动到z
if( 1 == n )
{
printf("%c-->%c\n", x, z);
}
else
{
//第三要素：找出函数的等价关系式，并不考虑具体的移动过程，仅考虑完成任务
move(n-1, x, z, y); // 将 n-1 个盘子从x借助z移到y上
printf("%c-->%c\n", x, z);// 将第n个盘子从x移到z上
move(n-1, y, x, z); // 将 n-1 个盘子从y借助x移到z上
}
}
int main()
{
int n;
printf("请输入汉诺塔的层数: ");
scanf("%d", &n);
printf("移动的步骤如下: \n");
move(n, 'X', 'Y', 'Z');
return 0;
}