我是递归盲~~~

蔚落 2022-06-13 10:07 191阅读 0赞

奈何~~我对递归完全没办法~各种不理解~~我决定把各种简单的复杂的递归题都放在这~~我就看就想就调试~我不信了，我还能被递归吓死！！！

**一.函数pow(x,y)实现运算x^y，即x的y次方，这里x和y都为整数。**

算法的基本思想是，减少乘法次数，重复利用结算结果，例如：  
x^4，如果逐个相乘的话，需要四次乘法。如果我们这样分解(x^2)\*(x^2)就只需要2两次乘法，因为x^2的结果我们可以重复利用。所以我们最好做对称的分解指数y，然后求x^(y/2)的平方。

具体算法如下：  
1 如果y为偶数，直接计算mypow(x, y/2)\*mypow(x, y/2)；  
2 如果y为奇数，则y-1为偶数，回到了第一种情况。

#include <iostream>
    using namespace std;
    
    int mypow(int x,int n)
    {
        if(n == 1)
        {
             return x;
        }
        int result;
        int temp = mypow(x,n/2);
        if(n%2 != 0)
        {
               result = x * temp * temp;       
        }
        else
        {
            result = temp * temp;
        }
        return result;
    }
    
    int main()
    {
        int x = 3;
        int n = 4;
        cout<<mypow(x,n)<<endl;
        
        system("pause");
    }

自己的想法：一层一层调用后，执行到n==1,return x;则temp = x= 3;这个时候n= 2,所以result= temp\*temp= 3\*3=9;然后return reslut;则temp = result = 9;这个时候

n= 4,result=temp\*temp=9\*9=81;结束函数。（PS：估计是对的把~我自己想的~）

**二.用递归函数完成以下运算：sum(n)=12\+22\+…+n2**

函数的原型如下：long sum(int n);   该函数完成12\+22\+…+n2的运算，并返回运算结果，其中n>0。

long sum(int n)
    {
      if(n==1)
             return 1;
      else
             return n*n+sum(n-1);
    }

**三.求下列递归函数的结果**

int a(int m, int n)  
\{   
    if ( m==0 )  
    \{   
        return n+1;  
    \}   
    else if ( n==0 )  
    \{   
        return a(m-1,1);  
    \}  
    else  
    \{   
        return a(m-1,a(m,n-1));  
    \}  
\}  
求a（3,3）。

思路：

f(0,n) =n+1;  
f(1,0)=f(0,1)=2;  
f(1,1)=f(0,f(1,0))=f(0,2)=3;  
f(1,2)=f(0,f(1,1))=f(0,3)=4;  
..  
f(1,n)=f(0,f(1,n-1)) =n+2;  
  
f(2,0)=f(1,1)=3;  
f(2,1)=f(1,f(2,0))=f(1,3)=5;  
f(2,2)=f(1,f(2,1))=f(1,f(1,f(2,0)))=7;  
f(2,3)=f(1,f(2,2))=f(1,7)=9;  
所以f(2,n)= 2\*n+3;  
  
同理 f(3,0)=f(2,1)=5;  
f(3,1)=f(2,f(3,0))=13;  
f(3,2)=f(2,f(3,1))=f(2,13)=29;  
f(3,3)=f(2,f(3,2))=61;

**四.如果表A中所有元素(a1,a2,…,an)与表B的一个顺序子表(bk,bk+1,…bk+n-1)完全相同（即a1=bk,a2=bk+1,…an=bk+n-1），则称表A包含在表B中。设ha，hb为带头结点的单链表，分别表示有序表A和B，下面的函数用于判别表A是否包含在表B中，若是，则返回true，否则返回false。（提示：用递归实现）**

\#definetrue 1

\#definefalse 0

\#defineNULL 0

typedefstruct node\{

int data;

struct node \*next;

\}node,linklisttype;

intinclusion(linklisttype \*ha, linklisttype \*hb)\{

linklisttype \*pa, \*pb;

pa = ha->next;

pb = hb->next;

(1)     ;