C语言学习笔记——递归函数

C语言学习笔记

递归函数

在本章递归函数的学习过程中，我们将举出几个典型的递归例子，以及三种理解递归运行的方法。

概念

• 函数自己调用自己就是递归函数了
• 本质还是一个循环，因此也有可控循环的三要素，即循环控制变量，且有初始值，以及循环控制变量的变化，循环停止的条件。

递归函数对比循环（理解一）

	#include <stdio.h>
	void fun(int n)
	{
		if (n > 0)
		{
			printf("%d ",n);
			fun(n-1);
		}
		
	}
	int main()
	{
		fun(5);
		return 0;
	}

这就是一个简单的递归函数，要注意的是在函数内部再次调用的时候参数变成了n-1，这样的目的是使函数获得循环控制变量的变化，以及循环停止的条件。

• 也就是说，递归函数的循环是这样的函数

    void fun (int n)
    {
    	if (n > 0)
    	{
    		（这里是要被循环执行的代码）
    		fun(n-1);
    	}
    }
  

递归函数的展开（理解二）

	#include <stdio.h>
	void fun(int n)
	{
		if(n>0)
		{
			printf("%d\n",n);
			fun(n-1);
			printf("%d\n",n);
		}	
	}
	
	int main()
	{ 
		fun(4);//结果是4 3 2 1 1 2 3 4 
		return 0;
	}

• 下面通过该图详细介绍该类型递归函数运作性质
  3 2 1 1 2 3 4
  return 0;
  }

• 下面通过该图详细介绍该类型递归函数运作性质
  

递归函数的通项公式（理解三）

• 以斐波那契数列为例，表示递归函数的通向公式，这也是递归函数的理解三：

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

在printf中函数的调用，改变fun后面的内容，则会得到斐波那契数列各项的值。

• 这样的递归执行逻辑如下（以fun（5）为例）。

递归函数的优缺点

• 首先递归的效率比循环低，这是因为函数要经常涉及地址的跳转。
• 递归难于阅读，难于维护
• 在某些情况下，递归的写法更简洁，但是并不能增加效率，大多情况还是用循环（这也是递归的唯一优点）
• 递归的层数不能太多，否则会stack overflow
• 什么时候用递归什么时候用循环？——能用循环就用循环

参数个数不确定的函数

• 函数头写法void fun(int a, ...);

• 注意点：第一个参数指定未知参数的个数，因此在调用的时候，注意fun(3, 12, 34, 56)以此类推。

• 那对于上述的函数调用，在函数体内如何能取到后面的三个数呢？
  

    	va_list ap;
    	va_start(ap,a);
  

• 这两行代码的意义分别是声明一个参数数组，和将参数装进数组（定义）。

    	printf("%d\n",va_arg(ap,int));
    	printf("%lf\n",va_arg(ap,double));
    	printf("%d\n",va_arg(ap,int));
  

• ap是数组名，这个函数是取函数数组内的参数。注意只能进行顺序的取参数，不能跳转所以循环取也是合法的。
  va_arg(ap,int);可以参与各种运算，不只是像这样打印。

• 这些以va开头的函数的头文件都在<stdarg.h>内。

方括号的三种作用

• 声明变量的时候用[]，表示声明的是数组变量
• 函数参数有[]，此时仅表示指针
• 地址+[]，表示下标运算。