函数的递归调用例题，最简单的递归函数

大家好，今天给各位分享函数的递归调用例题的一些知识，其中也会对最简单的递归函数进行解释，文章篇幅可能偏长，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在就马上开始吧！

c语言中,一个函数可以调用其他函数,不能调用自己

错，函数可以调用自己，函数自己调用自己的这种调用方式称为函数的递归调用,我给你举个列子：

intcalc(intnum){

if(num==0){

return0;

}else{

returnnum*calc(num-1);

}

}

这个函数就是利用递归求任意一个整数的阶乘

求递归算法的时间复杂度例题及答案

(1)递归执行过程

例子：求N!。

这是一个简单的"累乘"问题，用递归算法也能解决。

n!=n*(n-1)!n>1

0!=1,1!=1n=0,1

因此，递归算法如下：

Java代码

fact(intn){

if(n==0||n==1)

return1;

else

returnn*fact(n-1);

}

以n=3为例，看运行过程如下：

fact(3)-----fact(2)-----fact(1)------fact(2)-----fact(3)

------------------------------>------------------------------>

递归回溯

递归算法在运行中不断调用自身降低规模的过程，当规模降为1，即递归到fact(1)时，满足停止条件停止递归，开始回溯(返回调用算法)并计算，从fact(1)=1计算返回到fact(2);计算2*fact(1)=2返回到fact(3)；计算3*fact(2)=6，结束递归。

算法的起始模块也是终止模块。

(2)递归实现机制

每一次递归调用，都用一个特殊的数据结构"栈"记录当前算法的执行状态，特别地设置地址栈，用来记录当前算法的执行位置，以备回溯时正常返回。递归模块的形式参数是普通变量，每次递归调用得到的值都是不同的，他们也是由"栈"来存储。

(3)递归调用的几种形式

一般递归调用有以下几种形式(其中a1、a2、b1、b2、k1、k2为常数)。

<1>直接简单递归调用：f(n){...a1*f((n-k1)/b1);...};

<2>直接复杂递归调用：f(n){...a1*f((n-k1)/b1);a2*f((n-k2)/b2);...};

<3>间接递归调用：f(n){...a1*f((n-k1)/b1);...}，

g(n){...a2*f((n-k2)/b2);...}。

2.递归算法效率分析方法

递归算法的分析方法比较多，最常用的便是迭代法。

迭代法的基本步骤是先将递归算法简化为对应的递归方程，然后通过反复迭代，将递归方程的右端变换成一个级数，最后求级数的和，再估计和的渐进阶。

<1>例：n!

算法的递归方程为：T(n)=T(n-1)+O(1);

迭代展开：T(n)=T(n-1)+O(1)

=T(n-2)+O(1)+O(1)

=T(n-3)+O(1)+O(1)+O(1)

=......

=O(1)+...+O(1)+O(1)+O(1)

=n*O(1)

=O(n)

这个例子的时间复杂性是线性的。

<2>例：如下递归方程：

T(n)=2T(n/2)+2,且假设n=2的k次方。

T(n)=2T(n/2)+2

=2(2T(n/2*2)+2)+2

=4T(n/2*2)+4+2

=4(2T(n/2*2*2)+2)+4+2

=2*2*2T(n/2*2*2)+8+4+2

=...

=2的(k-1)次方*T(n/2的(i-1)次方)+$(i:1~(k-1))2的i次方

=2的(k-1)次方+(2的k次方)-2

=(3/2)*(2的k次方)-2

=(3/2)*n-2

=O(n)

这个例子的时间复杂性也是线性的。

<3>例：如下递归方程：

T(n)=2T(n/2)+O(n),且假设n=2的k次方。

T(n)=2T(n/2)+O(n)

=2T(n/4)+2O(n/2)+O(n)

=...

=O(n)+O(n)+...+O(n)+O(n)+O(n)

=k*O(n)

=O(k*n)

=O(nlog2n)//以2为底

一般地，当递归方程为T(n)=aT(n/c)+O(n),T(n)的解为：

O(n)(a<c&&c>1)

O(nlog2n)(a=c&&c>1)//以2为底

O(nlogca)(a>c&&c>1)//n的(logca)次方，以c为底

上面介绍的3种递归调用形式，比较常用的是第一种情况，第二种形式也有时出现，而第三种形式(间接递归调用)使用的较少，且算法分析

比较复杂。下面举个第二种形式的递归调用例子。

<4>递归方程为：T(n)=T(n/3)+T(2n/3)+n

为了更好的理解，先画出递归过程相应的递归树：

n-------->n

n/32n/3-------->n

n/92n/92n/94n/9-------->n

...............................

--------

总共O(nlogn)

累计递归树各层的非递归项的值，每一层和都等于n，从根到叶的最长路径是：

n-->(2/3)n-->(4/9)n-->(12/27)n-->...-->1

设最长路径为k，则应该有：

(2/3)的k次方*n=1

得到k=log(2/3)n//以(2/3)为底

于是T(n)<=(K+1)*n=n(log(2/3)n+1)

即T(n)=O(nlogn)

由此例子表明，对于第二种递归形式调用，借助于递归树，用迭代法进行算法分析是简单易行的。

c语言，利用递归函数调用方式，将所输入的5个字符，以相反顺序打印出来

#include<stdio.h>voidf(intn){charch;if(n>0){ch=getchar();f(n-1);}elsereturn;printf("%c",ch);}intmain(void){f(5);printf("\n");return0;}

递归函数详细讲解

（1）边界条件：确定递归到何时终止，也称为递归出口。

（2）递归模式：大问题是如何分解为小问题的，也称为递归体。递归函数只有具备了这两个要素，才能在有限次计算后得出结果

在递归函数中，调用函数和被调用函数是同一个函数，需要注意的是递归函数的调用层次，如果把调用递归函数的主函数称为第0层，进入函数后，首次递归调用自身称为第1层调用；从第i层递归调用自身称为第i+1层。反之，退出第i+1层调用应该返回第i层。

一个递归函数的调用过程类似于多个函数的嵌套的调用，只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行，系统需设立一个工作栈。具体地说，递归调用的内部执行过程如下：

（1）运动开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；

（2）每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈；

（3）每次递归调用结束后，将栈顶元

js类中递归调用

你好，这样是调用不到的，createA是内部函数，或者说他是A创建的对象的函数，应该像你test方法使用中那样调用。

用C语言，写一个函数用于计算1！+2！+3！+…+n！的值（使用函数递归完成）

#include<iostream.h>

intfun1(intn)

{

intsum=1;

for(inti=1;i<=n;i++)

sum*=i;

returnsum;

}

intfun(intn)

{

intsum=0;

if(n==1)return1;

elsesum+=fun1(n--);

returnsum;

}

voidmain()

{

intn,sum=0;

cout<<"inputn"<<endl;

cin>>n;

for(inti=1;i<=n;i++)

sum+=fun(i);

cout<<sum<<endl;

}

如果你还想了解更多这方面的信息，记得收藏关注本站。