网站开发只要,网页版微信登录入口手机,陕西专业网站开发联系电话,住房和城建设网站首页前言与概述
本文章将通过多个代码并赋予图示#xff0c;详细讲解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的每一位。在控制台上输入数字123scanf()函数读入用户输入的数值并赋予变量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*424。下面设计一个函数用于根据用户输入的值求出对应的阶乘。
如果用户输入的数小于等于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 * 12 * 1的值并返回到上一个函数步骤5。函数得到返回值2并将x * 23 * 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就成为新的第二个元素。
