考试2016年秋程序员软考( )

在单 CPU 计算机系统中,完成相同功能的递归程序比非递归程序【 】

A、运行时间更短,占用内存空间更少

B、运行时间更长,占用内存空间更多

C、运行时间更短,占用内存空间更多

D、运行时间更长,占用内存空间更少

运行时间更长,占用内存空间更多

完成相同功能的递归程序与非递归程序相比,会增加函数调用过程中必需的参数传通。控制转移和现场保护等处理,因此递归程序运行时需要更多的运行时间,占用更多内存空闻。

面试题2016年腾讯公司校园招聘( )

递归函数最终会结束,那么这个函数一定【 】

A、使用了局部变量

B、有一个分支不调用自身

C、使用了全局变量或者使用了一个或多个参数

D、没有循环调用

有一个分支不调用自身

1、局部变量只是在调用局部范围有效,出了这次调用的范围就无效了,它不能控制递归的结束。

2、递归函数中,如果没有一个分支不调用自身,递归就不会结束。

3、使用全局变量或使用一个或多个参数的确可以控制递归的结束,但题目中指出了"一定"。答案是并不是只有这两种方式。

考研1997年中国科学技术大学( )

对于正整数n ,输出其和等于n且满足以下限制条件的所有正整数的和式,组成和式的数字自左至右构成一个非递增的序列。如 n = 4 ,程序输出为:

4 = 4

4 = 3 + 1

4 = 2 + 2

4 = 2 + 1 + 1 

4 = 1 + 1 + 1 + 1

test 是实现该功能的 C 程序段,请将未完成的部分补足,使之完整。

test 函数为一递归函数,参数 n 为被分解和式的数, k 为当前的分解深度。

算法思想是对 n 的所有合理的和式分解,将分解出的数(称为和数)存于二数组 a[]中。当其中一个分解己不再需要进一步进行时,即找到一个解,将存于 a[] 中的一个完整和式的和数输出。当还需要进一部分解时,以要进一部分解的数及分解深度为参数,递归调用 test 函数。

#define MAXN 100
int a[MAXN];
test(int n,int k){
    int i,j;
    for (j=__________;j>=1;j--){
        a[k]=j; 
        if (__________){
            printf ( "%d = %d" , a[0],a[l]);
            for (i = 2 ; i < = k ; i + + )
                printf ( " + % d " , a[i]);
            printf ( "  n " );
        }else test(__________,k + l );
    }
}
(1)n (2) j==n (3) n-j

考研1996年清华大学( )

写出和下列递归过程等价的非递归过程。

void test(int sum){
    int a;
    scanf("%d",&a);
    if(a==0) sum=1;
    else{
        test(sum);
        sum=sum*a;
    }
    pritf("%d",sum);
}

#define STACKSIZE 100
typedef struct {
    DataType  items[STACKSIZE];
    int  top;
}SqStack;

SqStack stack;
int sum=1;

void test(){
    InitStack(stack);
    scanf("%d",&a);
    while(a!=0){
        push(stack,a);
        scanf("%d",&a);
    }
    printf("%d",sum);
    while(!EmptyStack(stack)){
        sum=sum*pop(stack);
        printf("%d",sum);
    }
}

此题的核心语句为: test (sum ) ;sum=sum * a ;

而 test 由于是递归调用,实际上完成一个“多次读入 a "的任务。只要 a != 0 就不停地读入,当 a =0 时,使 sum = 1。再通过不停地返回到上一层的调用过程实现把当前调用已经读入的全部 a 反向(与读入的顺序相反)逐个相乘。

由此可见,算法分成两部分:一部分是读入 a 并保存,另一部分是求出数 1 与当前已经读入所有 a 的反向相乘的乘积.

考研1995年北京航空航天大学( )

一般情况下,将递归转换成等价的非递归算法应该设置【】

A、堆栈

B、队列

C、线性表

D、数组

堆栈
堆栈的用途之一就是将递归转化为非递归。