C语言函数递归

前言与概述

本文章将通过多个代码并赋予图示，详细讲解C语言函数递归的定义和函数递归的运算过程。

函数递归定义

程序调用自身的编程技巧称为递归。递归作为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归策略只需要少量的程序便可以描述出解题过程中所需要的多次重复计算，大大节省了程序的代码量，递归的主要思考方式在于大事化小。

最简单的递归

在main()函数体内调用main()函数，这是最简单的函数递归。当然，这样的函数递归是错误的，因为main()函数被不断的调用，导致陷入死递归。

示例代码：

//最简单的函数递归
#include <stdio.h>
int main()
{printf("Good!!\n");main();return 0;
}

运行结果：

 

栈溢出

Stack overflow:栈溢出。在计算机内存中，主要分为三大区：栈区、堆区、静态区。栈区存放着局部变量、函数形参、函数返回值等临时性变量。堆区主要用于动态内存分配。静态区主要存放全局变量和静态变量。如果我们把栈区单独拿出，当程序进入main()函数中，main()函数会向栈区申请空间，于是，main()函数会得到一片空间，称为main()函数的栈帧空间。在main()函数体内定义的局部变量会存放在main()函数的栈帧空间里。如果main()函数调用了函数，调用的这个函数同样也会向栈区申请空间。但是栈区的空间是有限的，如果不停的调用函数，就会不停的占用栈区空间，直到栈区空间被耗尽，就会导致栈溢出。当函数完成调用，就会自动销毁，并释放空间。

 

 

打印一个数的每一位

算法

现在有一个整数1234，按照顺序打印这个数的每一位。

整数1234最容易打印的数是4，只需要将这个整数模10（%10）就可以得到。然后将整数1234除10，就可以去掉最后一位数字。接着将得到的整数123模10，打印得到的数字3。再将这个整数除以10，去掉最后一位3，得到整数12。以此类推，当这个整数小于10，就可以直接打印。

% 10 用于得到最后一位；/ 10 用于去掉最后一位。

定义一个函数，用于打印整数的每一位；定义变量number将读取的数值作为实参传给函数。函数会通过对10取模，打印整数的最后一位。接着将整数的值除以10，作为新的实参传给函数。如果整数的值大于9，就重复执行打印、调用函数。否则，只打印不调用函数。

 

如果函数体内先打印后调用函数，得到的结果就是将原整数逆序打印。

 

所以可以先调用函数后打印，这样得到的结果就是将原整数顺序打印。

示例代码

//先调用后打印
#include <stdio.h>
void print(int x)
{if (x > 9){print(x / 10);printf("%d ", x % 10);}else{printf("%d ", x);}
}
int main()
{int number = 0;scanf("%d", &number);print(number);return 0;
}

运行结果

 

 函数递归运行过程

 

 如果我们想在屏幕上按顺序打印整数123的每一位。在控制台上输入数字123，scanf()函数读入用户输入的数值，并赋予变量number。main()函数调用print()函数，把变量number的值作为形参传给print()函数（步骤1）。此时形参x的值是123。x的值大于9，条件成立，将变量x的值除以10的结果作为实参传给print()函数（步骤2）。此时，形参x的值是12，大于9，条件成立，将变量x的值除以10的结果作为实参传给print()函数（步骤3），此时，形参x的值是1，条件不成立。在屏幕上打印变量x的值1。遵循着“从哪里来回到那里去”的原则，返回到上一个函数（步骤4），并直接向下执行，此时，形参x的值是12，在屏幕上打印数字2，并返回到上一个函数（步骤5）此时，形参x的值是123，在屏幕上打印数字3。返回到main()函数（步骤六）。

求n的阶乘

算法

一个数的阶乘就是从1开始，每次乘的数都比上一个乘的数多一，直到乘的数等于它本身。0的阶乘等于1。如4的阶乘就等于1*2*3*4=24。下面设计一个函数，用于根据用户输入的值，求出对应的阶乘。

如果用户输入的数小于等于1，那么n的阶乘就是1；否则，n的阶乘就是n *（n - 1）的阶乘。

示例代码：

//求n的阶乘
#include <stdio.h>
int times(int x)
{if (x <= 1){return 1;}else{return x * times(x - 1);}
}
int main()
{int number = 0;scanf("%d", &number);int result = times(number);printf("%d", result);return 0;
}

运行结果

 

函数递归调用过程 

如果我们想知道3的阶乘，在控制台中输入数字3。scanf()函数从控制台中读取数字3，并赋予变量number。定义变量result，调用times()函数，将变量number的值作为实参传给函数（步骤一）。形参x得到变量number的值3。形参x的值大于1，条件不成立。调用times()函数，并将x - 1的值作为新的实参传给times()函数（步骤2）。此时形参x的值是2，条件不成立，调用times()函数，并将x - 1的值作为新的实参传给times()函数（步骤3）。此时形参x的值是1，条件成立，返回数字1。返回到上一个函数（步骤4），计算x * 1（2 * 1）的值并返回到上一个函数（步骤5）。函数得到返回值2，并将x * 2（3 * 2）的值返回到原调用函数处（步骤6）。变量result得到返回值6，并打印变量result的值。

递归与迭代

区别

迭代具有运行效率高的优点，但是代码量相对较大。递归整体上代码更加简洁，可读性高，但是可能出现栈溢出、运行效率低等问题。

求第n个斐波那契数（递归）

计算方法

什么是斐波那契数列？

1  1   2   3   5   8   13   21   34   55

斐波那契数列的第n个数（n >= 3）等于前两个数之和。

如果n的值小于等于2，那斐波那契数是1，如果n的值大于2，那么该斐波那契数等于第n - 1的斐波那契数加上第n - 2的斐波那契数。

示例代码（递归实现）

//求第n个斐波那契数
#include <stdio.h>
int fib(int x)
{if (x <= 2){return 1;}else{return fib(x - 1) + fib(x - 2);}
}
int main()
{int number = 0;scanf("%d", &number);int result = fib(number);printf("%d", result);return 0;
}

 运行结果 （递归实现）

不足之处 

虽然使用递归可以求出第n个斐波那契数，但如果输入n的值较大，就可能需要计算很长时间，甚至会导致程序崩溃。这主要是因为代码进行大量重复多余的计算。比如求第40个斐波那契数，仅第3个斐波那契数就重复计算了39088168次。于是，我们可以使用迭代来快速寻找到想要的值。

 

示例代码（迭代实现）

//求第n个斐波那契数非递归
#include <stdio.h>
int main()
{int number = 0;scanf("%d",&number);int a = 1;int b = 1;int c = 0;int temp = number;if (temp <= 2){c = 1;}else{while (temp - 2 >= 1){c = a + b;a = b;b = c;temp = temp - 1;}}printf("%d", c);return 0;
}

运行结果 （迭代实现）

代码分析

定义变量a保存第一个元素，定义变量b保存第二个元素，定义变量c保存第三个元素。如果输入的值小于等于2，那么变量c的值就是2。如果输入的值大于2，那么变量c的值就等于变量a的值加上变量b的值。把变量b的值赋予变量a，变量a就成为新的第一个元素，把变量c的值赋予变量b，变量b就成为新的第二个元素。