Hi,大家好,我是编程小6,很荣幸遇见你,我把这些年在开发过程中遇到的问题或想法写出来,今天说一说
c语言递归函数的例子_递归函数简单实例,希望能够帮助你!!!。
问题描述:斐波那契数列是以1为首项,1为第二项,其他项都为前面两项之和的数列。如:1、1、2、3、5…求斐波那契数列的第n项。
实现方法:采用递归函数的方式,以此算出每项,求出所求项
注意斐波那契数列用此方式虽然简便,但是当项数很大时往往会运行超时 这时候就应该使用数组+while循环的办法
代码如下:
double Fibonacci(int n) {
if (n==1) {
return(1); } else if (n==2) {
return(1); } else {
return(Fibonacci(n-2)+Fibonacci(n-1)); } }
实现方法:我们使用辗转相除法:a对b取余,然后令a=b,b=a%b,直到b=0为止。
代码如下:
int gcd(int a, int b) {
if(b==0) return a; return gcd(b,a%b); }
实现方法:将函数的返回值改为n*(n-1)即可
代码如下:
int factorial(int n) {
if (n==1) return 1; return n*factorial(n-1); }
问题描述:
一块板上有三根针,即A、B、C,A针上套有64个大小不等的圆盘,大的在下,小的在上,要把64个圆盘从A针移到C针上,每次只能移动一个圆盘,移动可以借助B进行。但在任何时候,任何针上的圆盘必须保证大盘在下,小盘在上,求移动的步骤。
实现方法:这是一个典型的递归函数问题,我们先来假设有3个盘子,那么要将三个盘子从A盘移动到C盘,我们来模拟一下步骤:
1.A->C
2.A->B
3.C->B
4.A->C
5.B->A
6.B->C
7.A->C
通过观察我们发现,这个问题就相当于将A针的n-1个盘移动到B针,然后再将A针的一个盘移动到C针,最后再将B针上的n-1盘移动到C针,递归结束的条件是n=1,也就是A针上只有一个盘。
代码如下:
#include<stdio.h> void hanoi(int n, char a, char b, char c) {
if (n==1) {
printf("%c->%c\n",a,c);//将最后一个盘移动到C针 } else {
hanoi(n-1,a,b,c);//将A针的n-1个盘移动到B针 printf("%c->%c\n",a,c); hanoi(n-1,b,a,c);//将B针的n-1盘移动到C针 } }
输入n=64的时候发现一直在输出停不下来,看来梵天的预言还是有点道理的。
问题描述:快速排序法是一种十分高效的排序方式,它的基本步骤是:
在n个待排序元素中选一个参照值k作为分割标准,把所有小于元素k的元素都移动k的前面,反之,比k大的元素都移动到k的后面,一趟排序完成,这样就分为两段,然后再对这两段执行相同的操作,直到子表的长度为。
实现方法:
我们将参照值k选为中点,然后设置一个i变量,一个j变量,i指向头,而j指向尾,通过移动指向,比较前后元素的大小,然后交换,在不满足i<j是停止循环。
代码如下:
int a[10000]; void swap(int *p,int *q)//这个函数的功能是交换两个元素 {
int t; t=*p,*p=*q,*q=t; } void quick_sort(int h,int t)//h代表头,t代表尾 {
if(h>=t) return ;//停止递归的条件 int x=a[(h+t)/2],i=h-1,j=t+1; //选取一个参照值x,这里我们选取中点 //可以将i,j看为指针,向前(向后)移动一位以保证指针有效 while(i<j)//此循环的功能是将大于参照值的元素移到参照值之后,小于参照值的元素移到之前 {
do i++;while(a[i]<x); do j--;while(a[j]>x);//移动指针并将其与参照值比较 if(i<j) swap(&a[i],&a[j]); } quick_sort(h,j); quick_sort(j+1,t);//前后两端分别递归 }
暂时就先写这些,如有如果发现错误请读者指正,感谢大家的支持。
今天的分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
上一篇
已是最后文章
下一篇
已是最新文章