运维开发网

C递归算法详细介绍

运维开发网 https://www.qedev.com 2022-05-12 16:51 出处:网络
什么是递归函数/方法?任何一个方法既可以调用其他方法也可以调用自己,而当这个方法调用自己时,我们就叫它递归函数或递归算法,接下来详细介绍需要了解的朋友可以参考下

什么是递归函数/方法?任何一个方法既可以调用其他方法也可以调用自己,而当这个方法调用自己时,我们就叫它递归函数或递归算法,接下来详细介绍需要了解的朋友可以参考下


1)1、1、2、3、5、8.......用递归算法求第30位数的值?

首先,我们可以发现从第三位开始的最后一位数字等于前两位数字之和,即:x=(x-1)+(x-2),xgt2;

这里需要不断添加,第一瞬间就会想到循环处理。我们尝试用数组加载这些值,即:

int[] a=new int[30]; a[0]=1; a[1]=1; for(int i=2;ilt;30;i++){ a[i]=a[i-1]+a[i-2];}

求a[29]的值就是第30位的值。递归怎么处理?定义相同的函数

fun(n){ return fun(n-1)+fun(n-2)//n为第几位数,第n位数返回值等于第n-1位数的值与第n-2位数的值之和}

只有ngt的时候;在这种情况下,我们可以做一个推论。

fun(n){ if(n==1 || n==2) return 1; else return fun(n-1)+fun(n-2);}

找乐子(30);


2)编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)斐波那契数列为:0、1、1、2、3、……,

即:

fib(0)= 0;

fib(1)= 1;

Fib(n)=fib(n-1)+fib(n-2)(当ngt1)何时

写为递归函数的有:

int fib(int n) {  if (n==0) return 0;   if (n==1) return 1;   if (ngt;1) return fib(n-1)+fib(n-2); }

递归算法的运行过程分为递归和回归两个阶段。在递归阶段,一个更复杂的问题(规模n)的解被推到一个比原问题更简单的问题(规模小于n)的解。

例如,在上面的例子中,求解fib(n)被推至求解fib(n-1)和fib(n-2)。也就是说,为了计算fib(n),首先要计算fib(n-1)和fib(n-2),然后再计算fib(n-3)和fib(n-4)。依此类推,直到fib(1)和fib(0)被计算出来,结果1和0可以分别立即得到。在递归阶段,必须有一个终止递归

情况。例如,在函数fib中,当n为1和0时。

在回归阶段,当得到最简单情况的解后,我们会一步一步的往回走,依次得到稍微复杂的问题的解。例如,在获得fib(1)和fib(0)之后,我们将返回获得fib(2)的结果,...,并且在获得fib(n-1)和fib(n-2)的结果后,我们将返回来获得fib(n)。

编写递归函数时,要注意对函数中局部变量和参数的了解仅限于当前调用级别。当递归函数被推到“简单问题”级别时,原级别中的参数和局部变量将被隐藏。在一系列“简单问题”层中,它们都有自己的参数和局部变量。

由于递归引起一系列的函数调用,并且可能有一系列的重复计算,所以递归算法的运行效率比较低。当递归算法可以很容易地转换成递归算法时,通常按照递归算法编写代码。比如上例中用来计算斐波那契数列第n项的函数fib(n)就应该采用递归算法,即从斐波那契数列的前两项开始,依次从前两项开始计算下一项,直到计算出所需的第n项。


3)求1+2+3+4+5+....+n的值Fun(n)=n+Fun(n-1)n=1时为1Fun(n){ if(n==1) return 1; else return n+Fun(n-1);}


4)有两个整数型数组,从小到大排列,编写一个算法将其合并到一个数组中,并从小到大排列public void Fun() { int[] a = { 1, 3, 5, 7, 9, 10 }; int[] b = { 2, 4, 6, 8, 11, 12, 15 }; int[] c = new int[a.Length + b.Length]; ArrayList al=new ArrayList(); int i=0; int j=0; while (i lt;= a.Length - 1 amp;amp; j lt;= b.Length - 1) { //循环比較把小的放到前面 if (a[i] lt; b[j]) { al.Add(a[i++]); } else { al.Add(b[j++]); } } //两个数组的长度不一样,必有个数组没比較完 while (i lt;= a.Length - 1)//加入a中剩下的 { al.Add(a[i++]); } while (j lt;= b.Length - 1)//加入b中剩下的 { al.Add(b[j++]); } for (int ii = 0; ii lt;= c.Length-1 ; ii++) { c[ii] = (int)al[ii]; } }


总结

本文到此为止。希望能帮到你,也希望你能多多关注

0

精彩评论

暂无评论...
验证码 换一张
取 消