递归（六）：递归小程序阅读

递归（六）：递归小程序阅读

阅读下列程序，写出程序执行后的输出结果。

1. 

#include <iostream>
using namespace std;
int fun(int x)
{
    int f;
    if (x<=2) f=1;
    else f= fun(x-1)+fun(x-2);
    return f;
}
int main()
{
    cout<<fun(8)<<endl;
    return 0;
}

分析：int fun(int x)函数通过递归求斐波那契数列第x项的值。递归终止时：f(1)=f(2)=1，递归式子为：f(n)=f(n-1)+f(n-2)。

程序输出结果为： 21

 

2.

#include <stdio.h>
int f(int n, int m)
{
      if (m>n) return 0;
      if (m==1) return n ;
      return  f(n-1,m-1) + f(n-1,m);
}
int main()
{
      printf("%d\n",f(5,3));
      return 0;
}

分析：int f(int n, int m)函数通过递归求从n个数中选出m个数的组合数。递归终止条件为：m>n（需要选出的数比待选数多，不可能选出，故返回0）或m=1（n个数中任选1个数有n种选择，故返回n）。递归式为：

           f(n,m) = f(n-1,m-1) + f(n-1,m)   当n>=m>1时。

      从n个数中选择出m个数可以看成两种情况：（1）选择第n个数，此时需要在前n-1个数中选择m-1个数，即调用f(n-1,m-1)；（2）不选择第n个数，此时需要在前n-1个数中选择m个数，即调用f(n-1,m)。

程序输出结果为： 10

 

3.

#include <stdio.h>
int f(int a,int b)
{
    if  (a%b)  return f(b,a%b);
    else return b;
}
int main()
{
    printf("%d\n",f(20,12));
    return 0;
}

分析：int f(int a,int b)函数的功能是求整数a和b的最大公约数。

程序输出结果为： 4

 

4.

#include <stdio.h>
int fun(int x)
{
    if (x<10) return x;
    else return x%10+fun(x/10);
}
int main()
{
    printf("%d\n",fun(19491001));
    return 0;
}

分析：int fun(int x) 函数的功能是求整数x的各位数字之和。递归终止条件为：x<10，即1位数的数字和是其本身；递归式含义为：若整数x的位数n>=2，则其各位数字和可以看成是其个位数字（x%10）加上其高n-1位数字组成的整数x/10的各位数字之和fun（x/10）。

程序输出结果为：25

 

5.

#include <stdio.h>
int f(int k)
{
    if (k<0)
       return k*2;
    else
       return f(k-2)+k;
}
int main()
{
    printf("%d\n",f(5));
    return 0;
}

分析：为求f(5)，要求f(3)+5；而f(3)=f(1)+3，f(1)=f(-1)+1，f(-1)=2*(-1)=-2，所以f(1)=-1，f(3)=2，f(5)=7。

程序输出结果为：7

 

6.

#include <stdio.h>
int f(int n, int m)
{

    int i, sum;
    if (m == 1) return 1;
    sum = 0;
    for (i = 1; i <=n; i++)
        sum += f(i, m - 1);
    return sum;
}
int main()
{
    printf("%d\n",f(5,3));
    return 0;
}

分析：为求f(5,3)，需求f(1,2)+f(2,2)+f(3,2)+f(4,2)+f(5,2)，

        f(1,2)=f(1,1)=1，

        f(2,2)=f(1,1)+f(2,1)=1+1=2，

        f(3,2)=f(1,1)+f(2,1)+f(3,1)=1+1+1=3， 

        f(4,2)=f(1,1)+f(2,1)+f(3,1)+f(4,1)=1+1+1+1=4

        f(5,2)=f(1,1)+f(2,1)+f(3,1)+f(4,1)+f(5,1)=1+1+1+1+1=5。

程序输出结果为： 15

扩展：若 将程序中的 “if (m == 1) return 1;”改写为“if (m == 1) return n;”，则

f(5,3)=1+(1+2)+(1+2+3)+(1+2+3+4）+（1+2+3+4+5）=35.

 

7.

#include <stdio.h>
void prim(int m, int n)
{
    if(m>n)
    {
         while(m%n != 0) n++;
         m /= n;
         prim(m, n);
         printf("%d*",n);
    }
}
int main()
{
    prim(60,2);
    return 0;
}

分析：void prim(int m, int n)函数的功能是将整数m从质因数n开始分解质因数。

程序输出结果为：5*3*2*2*

 

8.

#include <stdio.h>
void fun(char s[], int n)
{
    if (n<2)
        return;
    char t;
    t=s[0]; s[0]=s[n-1]; s[n-1]=t;
    fun(&s[1],n-2);
}
int main()
{
    char s[]="ABCDEFG";
    fun(s,7);
    printf("%s\n",s);
    return 0;
}

分析：void fun(char s[], int n)函数的功能是将具有n个元素的数组s逆序。递归终止条件为:n<2，当数组中元素个数不足2个时，直接返回；当元素个数超过2个时，将首尾元素交换，然后将中间n-2个元素逆序，即递归调用 fun(&s[1],n-2)。

程序输出结果为：GFEDCBA

 

原文链接:https://www.cnblogs.com/cs-whut/p/11141773.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有