C语言 函数递归

函数递归

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

优点

代码简洁清晰，可读性好

缺点

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

习题

1到n的和

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; 
}

运行结果：