递归算法公式,递归算法

递归算法公式,递归算法详细介绍

本文目录一览： 如何在excel表中计算递归函数？

你要的公式：
=MIN(IF(A2*0.9^ROW($1:$99)<=5,ROW($1:$99),))
数组公式，同时按下Ctrl+Shift+Enter结束输入。
=递减次数(A2,B2,C2)
Function 递减次数(a As String, b As String, c As String)
For i = 1 To 1000
If a * (1 - b) > c * 1 Then
n = n + 1
a = a * (1 - b)
Else
Exit For
End If
Next
递减次数 = n + 1
End Function
就是选择的 VLOOKUP函数 中的部分项目指向了被 引用的位置，而被引用的位置又涉及到了vlookup函数中的数据。
具体问题可以查看帮助中的 “循环引用”，举个简单例子：
你输入A1 公式 =B1+C1
B1中输入了 50
C1中输入了 =A1+20
结果就如出现该提示。
10*0.9^n>=5
两边除以10得：0.9^n>=0.5
两边取对自然数得：n*ln(0.9）>=ln(0.5)
n>=ln(0.5)/ln(0.9)
EXCEL的LN是计算自然对数的函数，计算得n>=6.578813479，也就是第一个整数解是7，EXCEL的计算和验算过程如下图：

递归算法

给你做一个简单的例子吧
比如说汉诺塔问题
10个汉诺塔的算法：
#include

#include

using namespace std;

void Move(int n,char i,char j)

{

fout<<"把"<
<n<<"号从"<<i<<"移动到"<<j<<endl;
}

void Fannoi(int n,char a,char b,char c)

{if(n==1)

{Move(1,a,c);

}

else

{Hannoi(n-1,a,c,b);

Move(n,a,c);

Hannoi(n-1,b,a,c);

}

}

int main()

{

fout<<“以下是10层汉诺塔的解法"<
<endl;
Hannoi(10,'a','b','c');

fout.close();

cout<<"输出结果完毕"<
<endl;
return 0;

}

递归算法

　　 递归算法流程

递归过程一般通过函数或子过程来实现。递归算法：在函数或子过程的内部，直接或者间接地调用自己的算法。

递归算法的特点

　　递归算法是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。 　　递归算法解决问题的特点： 　　(1) 递归就是在过程或函数里调用自身。 　　(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。 　　(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。 　　(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。

递归算法要求

　　递归算法所体现的“重复”一般有三个要求： 　　一是每次调用在规模上都有所缩小(通常是减半)； 　　二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)； 　　三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。

举例

　　描述：把一个整数按n(2<=n<=20)进制表示出来，并保存在给定字符串中。比如121用二进制表示得到结果为：“1111001”。 　　参数说明：s: 保存转换后得到的结果。 　　n: 待转换的整数。 　　b: n进制（2<=n<=20） 　　void 　　numbconv(char *s, int n, int b) 　　{ 　　int len; 　　if(n == 0) { 　　strcpy(s, ""); 　　return; 　　} 　　/* figure out first n-1 digits */ 　　numbconv(s, n/b, b); 　　/* add last digit */ 　　len = strlen(s); 　　s[len] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[n%b]; 　　s[len+1] = '\0'; 　　} 　　void 　　main(void) 　　{ 　　char s[20]; 　　int i, base; 　　FILE *fin, *fout; 　　fin = fopen("palsquare.in", "r"); 　　fout = fopen("palsquare.out", "w"); 　　assert(fin != NULL && fout != NULL); 　　fscanf(fin, "%d", &base); 　　/*PLS set START and END*/ 　　for(i=START; i <= END; i++) { 　　numbconv(s, i*i, base); 　　fprintf(fout, "%s\n", s); 　　} 　　exit(0); 　　} 　　

编辑本段递归算法简析（PASCAL语言）

　　递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写 　　程序能是程序变得简洁和清晰.

一 递归的概念

　　1.概念 　　一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数). 　　如: 　　procedure a; 　　begin 　　. 　　. 　　. 　　a; 　　. 　　. 　　. 　　end; 　　这种方式是直接调用. 　　又如: 　　procedure c(形参);forward; 　　procedure b; 　　局部说明 　　begin 　　. . 　　c(实参); 　　. . 　　end; 　　procedure c; 　　局部说明； 　　begin 　　. . 　　b; 　　. . 　　end; 　　这种方式是间接调用. 　　例1计算n!可用递归公式如下: 　　fac:=n*fac(n-1) {当n>0时} 　　fac(n)={ 　　fac:=1; { 当n=0时} 　　可编写程序如下: 　　program facn; 　　var 　　n:integer; 　　function fac(n:integer):real; 　　begin 　　if n=0 　　then fac:=1 　　else fac:=n*fac(n-1); 　　end; 　　begin 　　write('n=');readln(n); 　　writeln(n,'!=',fac(n):0:0); 　　end. 　　例2 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法. 　　设n阶台阶的走法数为f(n) 　　显然有 　　n=1 　　f(n)={ 　　f(n-1)+f(n-2) n>2 　　可编程序如下： 　　program louti; 　　var n:integer; 　　function f(x:integer):integer; 　　begin 　　if x=1 then f:=1 else 　　if x=2 then f:=2 else f:=f(x-1)+f(x-2); 　　end; 　　begin 　　write('n=');read(n); 　　writeln('f(',n,')=',f(n)) 　　end.

二 如何设计递归算法

　　1.确定递归公式 　　2.确定边界(终了)条件

三 典型例题

　　例3 汉诺塔问题 　　如图:已知有三根针分别用1,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子 　　从1针全部移到3针,移动规则是:使用2针作为过度针,每次只移动一块盘子,且每根针上 　　不能出现大盘压小盘.找出移动次数最小的方案. 　　程序如下: 　　program hanoi; 　　var 　　n:integer; 　　procedure move(n,a,b,c:integer); 　　begin 　　if n=1 then writeln(a,'->',c) 　　else begin 　　move(n-1,a,c,b); 　　writeln(a,'--->',c); 　　move(n-1,b,a,c); 　　end; 　　end; 　　begin 　　write('Enter n='); 　　read(n); 　　move(n,1,2,3); 　　end. 　　例4 快速排序 　　快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束. 　　程序如下: 　　program kspv; 　　const n=7; 　　type 　　arr=array[1..n] of integer; 　　var 　　a:arr; 　　i:integer; 　　procedure quicksort(var b:arr; s,t:integer); 　　var i,j,x,t1:integer; 　　begin 　　i:=s;j:=t;x:=b ; 　　repeat 　　while (b[j]>=x) and (j>i) do j:=j-1; 　　if j>i then begin t1:=b; b:=b[j];b[j]:=t1;end; 　　while (b<=x) and (i
<j) do i:="1" 　　if i<j then begin t1:="b[j];b[j]:=b;b:=t1;" end 　　until i="j;" 　　b:="x;" 　　i:="i+1;j:=j-1;" s<j quicksort(b,s,j); i<t quicksort(b,i,t); 　　end; 　　begin 　　write('input data:'); 　　for to n read(a); 　　writeln; 　　quicksort(a,1,n); 　　write('output 　　write(a:6); 　　end.
编辑本段{递归的一般模式}

　　procedure aaa(k:integer); 　　begin 　　if k=1 then (边界条件及必要操作) 　　else begin 　　aaa(k-1); 　　(重复的操作); 　　end; 　　end;

开放分类：

编程，计算机，算法

引自：http://baike.baidu.com/view/1733593.htm

</endl;
</endl;
</n<<"号从"<<i<<"移动到"<<j<<endl;

递归法求n阶勒让德多项式，Pn={1,n=0 x，n=1 （（2n-1）x-Pn-1（x）-（n-1）Pn-2（x））n,n)=1 有问题

是2return（c）
递归公式
1 (n=0)
pn(x)=x (n=1)
((2n-1)xpn-1(x)-(n-1)pn-2(x))/n (n>1)
例如：
#include

float p (int n,int x)

{

int f;

if(n<0)

{

f = -1;

printf("error, n should be larger than 0");

}

else if(n==0)

{

f = 1;

}

else if (n==1)

{

f = x;

}

else if (n>1)

{

f=((2*n-1)*x*p(n-1, x)-(n-1)*p(n-2,x))/n;

}

return f;

}

void main ()

{

int n,x;

printf("请输入n,x的值:");

scanf("%d%d",&n,&x);

printf("结果为:%d\n",p(n,x));

getchar();

}

扩展资料：

由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时，通常按递推算法编写程序。

例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法，即从斐波那契数列的前两项出发，逐次由前两项计算出下一项，直至计算出要求的第n项。

参考资料来源：百度百科-递归法

是2return（c）

代码中存在问题，其中是2return（c）。

递归公式：

1 (n=0)

pn(x)=x (n=1)

((2n-1)xpn-1(x)-(n-1)pn-2(x))/n (n>1)

在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。 递归一词还较常用于描述以自相似方法重复事物的过程。 例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。 也可以理解为自我复制的过程。

递归法执行过程：

递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。

也就是说，为计算fib(n)，必须先计算fib(n-1)和fib(n-2)，而计算fib(n-1)和fib(n-2)，又必须先计算fib(n-3)和fib(n-4)。依次类推，直至计算fib(1)和fib(0)，分别能立即得到结果1和0。在递推阶段，必须要有终止递归的情况。例如在函数fib中，当n为1和0的情况。

汉诺塔递归算法是什么？

汉诺塔递归算法是：f（n）=2^n-1。
汉诺塔，又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。
大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。
不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。
这需要多少次移动呢？这里需要递归的方法。假设有n片，移动次数是f（n）显然f（1）等于1，f（2）等于3，f（3）=7，且f（k+1）=2*f（k）+1。此后不难证明f（n）=2^n-1。n=64时。
假如每秒钟一次，共需多长时间呢：一个平年365天有31536000 秒，闰年366天有31622400秒，平均每年31556952秒，计算一下：13800709551615秒。
这表明移完这些金片需要5845.54亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

递归时间复杂度 推演计算

递归的时间复杂度计算较为麻烦。以下我们使用归并排序的例子，对递归复杂度进行推演。

假设现在有一个归并排序。他的运行总时间是 T（n） ，
我们通过将其分解成 2 个计算式，即 ： 2 * （T（n/2））+ n ，为什么加 n 呢？因为 n/2 只是递归计算的时间，实际还有合并的时间，在大部分递归中，不但有子任务的时间，还有合并子任务的时间也要计算（在递归计算中，子问题消耗的时间需要统计，合并子问题的结果所消耗的时间也要统计）。

现在，我们的公式是 2 * （T（n/2））+ n ，表达的是一颗高度是 1 的递归树：

如上图，我们需要把这颗递归树的 3 个节点的所有耗时都加上，最终的结果就是 T(N) ;
再看上图，我们递归了 1 层，如果递归 2 层、3层呢？

递归 2 层，表达式变为 4 *（T（n/4）)+ 2n .

递归 3 层，表达式变为 8 * （T（n/8）)+ 3n .

我们总结一下：

递归 2 层： 4（T（n/4）)+ 2n
递归 3 层： 8（T（n/8）)+ 3n
递归 4 层： 16（T（n/16）)+ 4n
······
递归 k 层： 2^k （T（n/2^k））+ kn

假设我们最终递归的结果是 1，那么：

T(n/2^k) = 1
·····反推 2^k = n
····· 那么 k = log2n

k 等于 log2N ，我们带入 k 到上面的公式： 2^k （T（n/2^k））+ kn ；

即 n + log2n * n ；

使用大 O 表达式，去除常数，低阶，系数，递归的时间复杂度为 O(nlogn) ;

关于递归树的推演，推荐观看一个视频，讲的很详细，地址： https://www.youtube.com/watch?v=bQi9BHCiusg

怎么用公式法求递归方程？

若数列H(n)的递推公式为：
H(n)-a1H(n-1)-a2H(n-2)-…-akH(n-k)=0,则一元k次方程xk-a1xk-1-a2xk-2-…-ak=0叫k阶
常系数递推公式的特征方程，其k个复数根叫特征根。由递推公式求通项公式要用。
数列H(n)的k个互不相同特征根为：q1,q2,…,qk,则k阶常系数递推公式的通解为：
H(n)= c1q1^n+ c2q2^n+…+ ckqk^n
其中的c1,c2,...,ck待定后就可得到一个特解。
(ckqk^n等于ck与qk的n次方的乘积)

汉诺塔递归算法是什么？

hanot (n-1,b,a,c);（解释：在把B塔上的(n-1))个借助A塔移动到C塔）
为了实现 n个盘从 借助c 从a 移动到 b
思路如下：
首先考虑极限当只有一个盘的时候，盘直接从 a -> b即可。
当有2个盘的时候，把1号盘从a -> c 然后 把2号盘 a->b 再 把 2好盘从 c - > b。
当有n个盘的时候，把 n-1个 盘 借助 b 移动到 c 然后将 n号盘从 a -> b。
这时候只要将 n-1想办法从c移动到 b 借助 a 那么就可以先把 n-2个盘借助b移动到a。
递归，就是在运行的过程中调用自己。
构成递归需具备的条件：
1，子问题须与原始问题为同样的事，且更为简单；
2，不能无限制地调用本身，须有个出口，化简为非递归状况处理。
在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。
以上内容参考：百度百科-递归公式

一列数的规则如下： 1、1、2、3、5、8、13、21、34...... 求第30位数是多少， 用递归算法实现。

832040
是832040
直接使用通项公式来计算.
递归公式:a(1)=1;a(2)=1;a(n)=a(n-1)=a(n-2)
如果项数非常巨大时,递归非常缓慢,要用到矩阵加速.

快速排序最差时间复杂度递归公式 t(n-1)

T(n) = n+T(n-1) =n+n-1+T(n-2)=...=n+(n-1)+(n-2)+...+1+T(0)=(1+n)*n/2=O(n^2)
T(n) = n+T(n-1) =n+n-1+T(n-2)=...=n+(n-1)+(n-2)+...+1+T(0)=(1+n)*n/2=O(n^2)
理论计算机研究中，衡量算法一般从两个方面分析：时间复杂度和空间复杂度。空间复杂度跟时间复杂度是类似的，下面简单解释一下时间复杂度：对于一个数据规模为n的问题，解决该问题的算法所用时间可以用含有n的函数T(n)来表示。
对于绝大多数情况，只需要了解算法的一般性能而不考虑细节，也就是说，我们只关心函数T(n)的表达式的形式，而不关心表达式的常数系数等与数据规模没有关系的量值。
对于函数T(n)，我们又进一步将它简化为O(n)，即只考虑算法平均运行时间的“瓶颈”，也就是T(n)表达式中，关于变量n增长最快的哪一项。
扩展资料：
二进制整数的基数排序是一个非常特殊的情形，因为只有两个数字 0 和 1，故每次将数据分成 2 个小组。假设所有数据属于[0，21+m-1], m 为一整数，则先根据最高位（m 位）的数字将数据分成 2 个小组，分别属于[0，2m-1]和[2m，21 + m-1]；
根据次高位（m-1 位）的数字将[0，2m-1]的数据分成 2 个小组，分别属于[0，21 - m-1]和[21 - m，2m-1]，将[2m，21 + m-1]的数据分成 2 个小组，分别属于[2m，2m+21 - m-1]和[2m+21 - m，21 + m-1]；……；这完全类似于快速排序的分治算法结构，因而可以类似于快速排序实现该算法。
参考资料来源：百度百科-超快速排序