递归算法是什么
递归算法(英语:recursion algorithm)在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。
递归式方法可以被用于解决很多的计算机科学问题,因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用,在这些语言中函数可以通过调用自身来进行递归。
计算理论可以证明递归的作用可以完全取代循环,因此在很多函数编程语言(如Scheme)中习惯用递归来实现循环。
递归程序
在支持自调用的编程语言中,递归可以通过简单的函数调用来完成,如计算阶乘的程序在数学上可以定义为:
这一程序在Scheme语言中可以写作:
(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))
不动点组合子
即使一个编程语言不支持自调用,如果在这语言中函数是第一类对象(即可以在运行期创建并作为变量处理),递归可以通过不动点组合子(英语:Fixed-point combinator)来产生。以下Scheme程序没有用到自调用,但是利用了一个叫做Z 算子(英语:Z combinator)的不动点组合子,因此同样能达到递归的目的。
(define Z (lambda (f) ((lambda (recur) (f (lambda arg (apply (recur recur) arg)))) (lambda (recur) (f (lambda arg (apply (recur recur) arg)))))))(define fact (Z (lambda (f) (lambda (n) (if (《= n 0) 1 (* n (f (- n 1))))))))
这一程序思路是,既然在这里函数不能调用其自身,我们可以用 Z 组合子应用(application)这个函数后得到的函数再应用需计算的参数。
尾部递归
尾部递归是指递归函数在调用自身后直接传回其值,而不对其再加运算。尾部递归与循环是等价的,而且在一些语言(如Scheme中)可以被优化为循环指令。 因此,在这些语言中尾部递归不会占用调用堆栈空间。以下Scheme程序同样计算一个数字的阶乘,但是使用尾部递归:
(define (factorial n) (define (iter product counter) (if (》 counter n) product (iter (* counter product) (+ counter 1)))) (iter 1 1))
能够解决的问题
-
数据的定义是按递归定义的。如Fibonacci函数。
-
问题解法按递归算法实现。如Hanoi问题。
-
数据的结构形式是按递归定义的。如二叉树、广义表等。
参考资料
百科-递归算法.百度百科
递归函数的类型与形式
递归函数简单来说就是函数调用自身,例如1,2,3,4四个人,年龄分别比后者大2岁,4是10岁
那么设age()函数,age=age(n-1)+2,又调用了函数本身
什么是递归函数 怎样实现递归
递归就是一个函数在它的函数体内调用它自身。执行递归函数将反复调用其自身,每调用一次就进入新的一层。递归函数必须有结束条件。
当函数在一直递推,直到遇到墙后返回,这个墙就是结束条件。
所以递归要有两个要素,结束条件与递推关系。
递归有两个基本要素:
(1)边界条件:确定递归到何时终止,也称为递归出口。
(2)递归模式:大问题是如何分解为小问题的,也称为递归体。递归函数只有具备了这两个要素,才能在有限次计算后得出结果
在递归函数中,调用函数和被调用函数是同一个函数,需要注意的是递归函数的调用层次,如果把调用递归函数的主函数称为第0层,进入函数后,首次递归调用自身称为第1层调用;从第i层递归调用自身称为第i+1层。反之,退出第i+1层调用应该返回第i层。
一个递归函数的调用过程类似于多个函数的嵌套的调用,只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行,系统需设立一个工作栈。具体地说,递归调用的内部执行过程如下:
(1)运动开始时,首先为递归调用建立一个工作栈,其结构包括值参、局部变量和返回地址;
(2)每次执行递归调用之前,把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈;
(3)每次递归调用结束后,将栈顶元
扩展资料:
递归就是某个函数直接或间接地调用了自身,这种调用方式叫做递归调用。说白了,还是函数调用。既然是函数调用,那么就有一个雷打不动的原则:所有被调用的函数都将创建一个副本,各自为调用者服务,而不受其他函数的影响。
你的ff函数,递归多少次,就有多少个副本,再利用内存的栈式管理,反向退出。这个最好找一下“栈”这方面的东西看看,挺容易的,就像子弹匣一样,先进后出。
从某种意义上说,这是不对的,因为就像刚才说的,一旦被调用,他将在内存中复制出一份代码,再被调用就再复制一份,换句话说,你可以吧同一个函数的多次调用理解称谓多个不同函数的一次调用,这样也会会简单些。
再说=1和=0是为什么退出。递归,很需要注意的就是死递归,也就是说,某一个函数进入了无限调用自身的情况,永无止境地消耗内存等资源,这在编程方面是一大忌。
但凡是递归的函数,一定会在某一个地方存在能够返回上一层函数的代码,否则必定死递归。ff函数中,那个else就是返回的出口,你可以这样想,如果没有那个if来进行判断,你递归到什么时候算完?ff是不是会一直调用自己。
因为一旦某个函数A中调用了函数B(或者自己),那么A中的代码会停在调用的位置,而转向B中去执行,同理,如果B又调用函数C,那么B又停在调用的位置,去执行C,如果无限调用,那么程序是永远不会结束的。
当然,也有这种情况,A调用B,然后继续自己的代码,不管B的死活,这种不在我们的讨论范围内,因为那牵扯到另一种编程方式:多线程。
参考资料:百度百科——递归函数
递归公式有哪几种方法
1、主方法求解递归式
一种求解大部分递归式的公式。给出递归式: T(n) = a * T(n/b) + f(n) ,其中a》=1,b》1,f(n)是给定的函数,T(n)是定义在非负整数上的递归式。
2、递归树求解
用主方法求解不了的递归式,我们可以用递归树来猜测解的上界,然后用代入法来证明解的正确性。递归树的求解精确度取决于画递归树的精确度。
3、代入法
比如我们求解,递归式T(n) = 2T(n/2)+n,我们猜测解是O(nlgn),我们要寻找到一个常数c,使得T(n)《=cnlgn。
即T(n) 《= 2c(n/2)lg(n/2)+n 《= cnlgn-cnlg2+n = cnlgn-cn+n
只要c》=1,T(n)《=cnlgn,所以我们的猜测是正确的。
要注意的是,代入法全凭经验,通常用递归树来确定上界,然后用代入法再证明。
扩展资料:
设p0,p1,…,pn,…是一个序列。如果pn和序列中在它前面的若干项联系起来的一个关系式对所有大于等于某个整数n0的整数n都是有效的,则称这个关系式为递归关系(recursive relation)式。
如:设(a0,a1,…,ar,…)是一个序列,把该序列中的ar和它前面的几个ai(0≤i《r)关联起来的方程称做一个递归关系。如关系式:ar=3ar-1 (r≥1)和错排数:Dn=(n-1)(Dn-1+Dn-2) (n=3,4,…),都是递归关系。
几个递归函数的意义
PDdigit(int d)函数的功能:按%c的格式打印十进制148对应的 ASCII编码字符
(‘0’的ASCII值是48,‘d’的ASCII值是100)。
void P(int n)函数功能:传入一个int型的参数n,如果n》10,则将n除以10,再次调用本函数,直到n《10为止,此时执行n《10时候的函数命令,当n《10时,执行PDdigit(int d)函数;
第二个函数,可能是我才疏学浅,至今不知道倒数第二行的R是个什么意思,变量么?
望采纳!!
C语言递归子函数
递归(recursion)就是子程序(或函数)直接调用自己或通过一系列调用语句间接调用自己,是一种描述问题和解决问题的基本方法。
递归通常用来解决结构自相似的问题。所谓结构自相似,是指构成原问题的子问题与原问题在结构上相似,可以用类似的方法解决。具体地,整个问题的解决,可以分为两部分:第一部分是一些特殊情况,有直接的解法;第二部分与原问题相似,但比原问题的规模小。实际上,递归是把一个不能或不好解决的大问题转化为一个或几个小问题,再把这些小问题进一步分解成更小的问题,直至每个小问题都可以直接解决。因此,递归有两个基本要素:
(1)边界条件:确定递归到何时终止,也称为递归出口。
(2)递归模式:大问题是如何分解为小问题的,也称为递归体。递归函数只有具备了这两个要素,才能在有限次计算后得出结果
汉诺塔问题:对汉诺塔问题的求解,可以通过以下3个步骤实现:
(1)将塔上的n-1个碟子借助塔C先移到塔B上;
(2)把塔A上剩下的一个碟子移到塔C上;
(3)将n-1个碟子从塔B借助塔A移到塔C上。
在递归函数中,调用函数和被调用函数是同一个函数,需要注意的是递归函数的调用层次,如果把调用递归函数的主函数称为第0层,进入函数后,首次递归调用自身称为第1层调用;从第i层递归调用自身称为第i+1层。反之,退出第i+1层调用应该返回第i层。采用图示方法描述递归函数的运行轨迹,从中可较直观地了解到各调用层次及其执行情况,具体方法如下:
(1)写出函数当前调用层执行的各语句,并用有向弧表示语句的执行次序;
(2)对函数的每个递归调用,写出对应的函数调用,从调用处画一条有向弧指向被调用函数入口,表示调用路线,从被调用函数末尾处画一条有向弧指向调用语句的下面,表示返回路线;
(3)在返回路线上标出本层调用所得的函数值。n=3时汉诺塔算法的运行轨迹如下图所示,有向弧上的数字表示递归调用和返回的执行顺序
三、递归函数的内部执行过程
一个递归函数的调用过程类似于多个函数的嵌套的调用,只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行,系统需设立一个工作栈。具体地说,递归调用的内部执行过程如下:
(1)运动开始时,首先为递归调用建立一个工作栈,其结构包括值参、局部变量和返回地址;
(2)每次执行递归调用之前,把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈;
(3)每次递归调用结束后,将栈顶元素出栈,使相应的值参和局部变量恢复为调用前的值,然后转向返回地址指定的位置继续执行。
上述汉诺塔算法执行过程中,工作栈的变化如下图所示,其中栈元素的结构为(返回地址,n值,A值,B值,C值),返回地址对应算法中语句的行号,分图的序号对应图中递归调用和返回的序号
递归函数的类型与形式
c语言所有递归都可以用非递归算法实现,最典型的就是迭代法,有时比递归更容易理解。至于递归中的形式参数是自动变量,没明白楼主的意思,形参就是形参啊,形参变量也是变量,其内存分配在栈区,随着函数的结束,其内存也会被释放,形参的生命周
求公式的递归函数
//应该可以一个搞定
/*
f(x,n)=x-x^2+x^3-x^4+···+(-1)^(n-1)*x^n
f(x,n-1)=x-x^2+x^3-x^4+···+(-1)^(n-2)*x^(n-1)
(-x)*f(x,n-1)=-x^2+x^3-x^4+……(-1)^(n-1)*x^n=f(x,n)-x
f(x,n)=x-x*f(x,n-1)
f(x,1)=x
*/
#include “stdafx.h“
#include 《stdio.h》
#include 《stdlib.h》
#include 《windows.h》
long int fun(int,int);
int main(int argc, char* argv)
{
int a,b;
while(1)
{
system(“cls“);
printf(“请输入x,n的值\n“);
scanf(“%d %d“,&a,&b);
if(a《=0||b《=0)
{
exit(0);
}
else
{
printf(“%d\n“,fun(a,b));
Sleep(1500);
}
}
return 0;
}
long int fun(int x,int n)
{
static long int r=x;
if(n==1)
{
r=x;
}
else
{
r=x-(x*fun(x,n-1));
}
return r;
}
递归函数的介绍
编程语言中,函数Func(Type a,……)直接或间接调用函数本身,则该函数称为递归函数。递归函数不能定义为内联函数。在数学上,关于递归函数的定义如下:对于某一函数f(x),其定义域是集合A,那么若对于A集合中的某一个值X0,其函数值f(x0)由f(f(x0))决定,那么就称f(x)为递归函数。
C语言递归函数1到n递归体是什么
C语言函数可以自我调用。如果函数内部一个语句调用了函数自己,则称这个函数是“递归”。递归是以自身定义的过程。