递归调用知识点-包含例题求解二分查找、青蛙跳台阶、逆序输出、阶乘、斐波那契、汉诺塔。

//推荐使用非递归，效率高思想：

一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题求解。

条件：

（1）自己调用自己

        void Fun() {

                Fun();//死递归

        }

（2）函数的退出条件

（3）问题规模逐渐缩小，直至最小问题规模 （形参控制问题规模）

使用：

定义函数名（将问题规模以实参形式输入）

{

        if（函数退出条件）{

                return；
        }

        递归算法；
}

eg:

//已知1，求前5的和

int GetSum (int n){

        if(n==1)

                return 1;

        GetSum (n-1)+n;

}

例题求解

eg1:

//求阶乘factorial

#include<stdio.h>

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

int main()
{
	printf("%d",factorial(3));
	return 0;
}

eg2:

//求斐波那契数列Fabonic

#include<stdio.h>
//递归实现
int Fabonic(int n)
{
	if(n == 2||n==1)// 终止条件
		return 1;
	return Fabonic(n - 1)+ Fabonic(n - 2);
}

int main()
{
	printf("%d", Fabonic(3));//1 1 2 3 5
	return 0;
}

#include<stdio.h>
//推荐使用非递归，效率高
//非递归实现
int Fibon1(int n) {
	int f1 = 1;
	int f2 = 1;
	int f3 = 1;
	for (int i = 3; i <= n; i++) {
		f3 = f1 + f2;
		f1 = f2;
		f2 = f3;
	}
	return f3;
}
int main()
{
	printf("%d", Fibon1(5));//1 1 2 3 5
}

eg3:

/*青蛙跳台阶问题：一只青蛙可以跳一级台阶或者2级，

*台阶数：1  2  3  4  5

*/跳法：   1  2  3  5  8

规律：n个台阶，先跳1个和前面（n-1）个的跳法+跳2个和（n-2）个的跳法，其实就是斐波那契数列。

#include<stdio.h>
int Frog(int n)
{
	if (n == 1)
		return 1;
	if (n == 2)
		return 2;
	return Frog(n - 1) + (n - 2);
}
int main()
{
	printf("%d", Frog(3));
	return 0;
}

eg4:

//int整型打印每一位元素值1234->4 3 2 1

#include<stdio.h>
int Show(int n)
{
	if (n == 0)
		return 0;
	printf("%d", n % 10);
	return Show(n / 10);
}
int main()
{
	Show(1234);
}

eg5:

//二分查找:前提有序

#include<stdio.h>
/*算法思想：左边left右边right位于两端，中间数mid与value比较
*如果mid>value,移位到mid-1与value比较
* 如果mid<value,移位到mid-1与value比较
*/

//递归实现二分查找-函数过程
int BinartSearPro(int* arr, int length, int left, int right, int value)
{
	if (left > right)//不存在该数据
		return -1;
	int mid = ((right - left) >> 1 + left);//“>>”右移位，(right - left) >> 1 意思为：(right - left) 除以1个2，这样写比较高级
	//int mid = ((right - left)/2 + left);
	if (arr[mid] == value)
		return mid;
	if (arr[mid] > value)//往小的那边即左边走
		return BinartSearPro(arr,length, left, mid - 1, value);
	else//往大的那边即右边走
		return BinartSearPro(arr,length, mid + 1, left, value);
}
//得到函数结果
int BinarySearRea(int* arr, int length, int value)
{
	int left = 0, right = length - 1;
	int index = BinartSearPro(arr, length, left, right, value);
	return index;//返回的是下标值
}

int main()
{
	int arr[] = { 1,2,3,4,5 };
	int len = sizeof(arr)/sizeof(arr[0]);
	printf("%d",BinarySearRea(arr, len,3));
	return 0;
}

eg6:

//汉诺塔

/*问题描述：n个盘子由大到小的堆在一起，从X处通过其余位置挪到Y
* 最终盘子仍然按照有大到小的顺序堆在Y处
*/

算法思想：欲将n个盘子从A处挪到C处，则需先将n-1个盘子从A处挪到B处，最后将最大的盘子n从A处挪到C。算法最终输出的结果为盘子挪动过程。

#include<stdio.h>


//输出函数
void Move(char x, char y)
{
	printf("%c->%c\n", x, y);//输出从x移动到y
}
//函数实现
void Hanoi(int n, int a, int b, int c) //n个盘子，abc三个位置，盘子最初位于a处，挪到c处
{
	if (n == 1)
		Move(a, c);
	else
	{
		Hanoi(n - 1, a, c, b);//将上面的n-1个盘子,从a通过c移动到b
		Move(a, c);//最后一个最大的盘子直接移动到c
		Hanoi(n - 1, b, a, c);//将上面的n-1个盘子,从b通过a移动到c
	}
}
int main()
{
	Hanoi(3, 'A', 'B', 'C');
}