C语言 函数递归

• 函数递归
• • 优点
  • 缺点
• 习题
• • 1到n的和
  • 斐波那契数列
  • 二分查找递归
  • 倒着打印数字

函数递归就是自己调用自己来解决问题。
在解决一个问题时，通过对问题进行一次次的分解得到所对应的值，然后再将每次解决的问题所得的值进行合并，最终解决问题。

代码简洁清晰，可读性好

1.时间和空间消耗较大。每一次函数调用都需要在栈中分配空间，往栈里面存入和取出数据都需要时间。
2.递归会造成栈溢出的问题。栈的大小是有限的，如果函数递归深度太大，所需要的内存空间可能会大于栈区的内存，会造成栈溢出的情况。

1到n的和

 int add(int n)
{
	if (n == 1)return 1;
	return add(n - 1) + n;
}

int main()
{
    printf("%d",add(4));
	return 0; 
}

运行结果：

斐波那契数列

 int fei(int n)
{
	if (n == 1 || n == 2)return 1;	
	return fei(n - 1) + fei(n - 2);
}

int main()
{
    printf("%d",fei(6));
	return 0; 
}

运行结果：

二分查找递归

 int BinarySearch0(int*nums,int target,int begin,int end) 
{
	
	int mid = begin + (end-begin) / 2;
	if (begin > end)return -1;
	if (nums[mid] > target)return BinarySearch0(nums, target, begin, mid - 1);
	else if (nums[mid] < target)return BinarySearch0(nums, target, mid + 1, end);
	else if (nums[mid] == target)return mid;
	
	return {};
}

int main()

{
    int nums[] = {1,2,3,4,6,7,8,9};
	printf("%d",BinarySearch0(nums,6,0,7));//打印出6所在的下标
	return 0; 
}

运行结果：

递归打印数字

 void a(int n)
{
	if (n != 0) 
	{
	   printf("<%d>", n % 10);
	   a(n / 10);
	}
}

int main()
{
    a(123123123);
	return 0; 
}

运行结果：