函数递归：递归的概念

递归是什么

函数递归就是自己调用自己，这里先写一个代码：

int main()
{printf("hehe\n");main();return 0;
}

这段代码打印"hehe"之后又调用了main（自己）函数，循环往复会直接进入死循环，最后会造成栈溢出

递归的限制

递归有两个条件：

1.每当进行一次递归，就会离限制条件越来越近

2.递归是由条件限制的，当满足一个条件之后，递归就不再继续

实操

1.阶乘

阶乘公式为：(n-1)! *n

例如：5！=4！*5

接下来把代码写上：
Fat:

int Fat(int a)
{if (a == 0)return 1;elsereturn Fat(a - 1) * a;
}

main:

int main()
{int a = 0;scanf_s("%d", &a);int c = Fat(a);printf("%d", c);return 0;
}

递归的过程

当我输入5的数字时因5!=0，程式会执行递推直到符合条件之后会开始执行回归

当我输入5时会输出120

输出正确

2.顺序打印数字

当输入一个四位数时输出时会输出顺序排列的数字

代码：

Print：

void Print(int a)
{if (a > 9){Print(a / 10);}printf("%d ", a % 10);
}

main:

int main()
{int a = 0;scanf_s("%d", &a);Print(a);return 0;
}

过程

过程就是将一个多位数的数字一个一个拆分直到小于9这个数字

递归与迭代

递归是一个好的编程技巧但也会被误用，当看到推导公式时就很容易写成递归的形式，如果不想写递归形式就可以使用迭代技巧

这是递归形式的代码：

int Fat(int a)
{if (a == 0)return 1;elsereturn Fat(a - 1) * a;
}

这是迭代的形式的代码：

int Fat(int a)
{int b = 0;int ret = 1;for (b = 1; b <= a; b++){ret *= b;}return ret;
}

使用迭代的方式写代码代码运行会比递归的效率更高

1.斐波那契数

斐波那契数组是将是前面加后面的数算出答案后再把算出的答案和位置b的数字相加变成新的答案，形式如下图：

图例：

下面是代码：

int Fib(int a)
{if (a <= 2)return 1;elsereturn Fib(a - 1) + Fib(a - 2);
}
int main()
{int a = 0;scanf_s("%d", &a);int b = Fib(a);printf("%d", b);return 0;
}

较小的数字会是正确的答案，可当我输入较大的数字呢？

运行结果：

出现了一长串的数字并且不知道是否正确，在代码中加上count来看看它算了几次

代码：

int count = 0;
int Fib(int a)
{if (a == 3)count++;if (a <= 2)return 1;elsereturn Fib(a - 1) + Fib(a - 2);
}
int main()
{int a = 0;scanf_s("%d", &a);int b = Fib(a);printf("%d\n", b);printf("count = %d", count);return 0;
}

运行结果：

在第50个斐波那契数时它算了五亿次，当中会有很多冗余的计算，是因为斐波那契数为c = a+b,倒过来为c-(a+b)   ，如下图：

用图展开后我们发现有很多重复计算的地方，这样造成了计算效率低下如果使用迭代的方式来写代码效率会大大的提升

int Fib(int d)
{int a = 1;int b = 1;int c = 1;while (d > 2){c = a + b;a = b;b = c;d--;}return c;
}

递归虽然好写，但不要啥都写成递归

总结：

递归的优缺点

递归

优点：
代码简洁，套公式就能写

缺点：

效率低下

迭代

优点：

代码执行效率高

缺点：

代码极为复杂