[Lemma 說明]

會寫 recursive 通常讓初學者覺得「很強、思緒很清晰」,就吾人所知會「避開用 recursive 」有以下二個原因

(1) stack overflow:若問題大(問題本身可能簡單,但recursive 會進行多次),recursive 所需之 stack 便大,若使用 stack 超過可用範圍,則會因 stack overflow 使得程式終止

(2) 速度「通常」比一般 loop 來得慢:存入 stack、取出 stack 仍需一點點時間 (雖這時間應不長)。故有另一門學問是,如何將 recursive 拿掉,化為一般之 loop。

會用 recursive 的原因,大多都是因「程式碼思緒看起來較清楚」、「減化開發時間 (如果 recursvie 熟練的話..)」而此系列文主要目的為「引導初學者」學習 recursive 之技巧,但不代表任何問題都適合 recursive 去解 (也可說絕大多數問題,能避免就避免)。放上我曾看過很認同的話

「遞迴只應天上有,凡人應當用迴圈」 

 


 這裡的數學問題都屬較簡單,分 itera 與 recursive 版本去解,將提到以下題目

  1. 1+2+...+n 
  2. 1-2+3-4+....+n
  3. 1+4+9+16+....+n*n 
  4. n!  ( 階層函式)
  5. fib (費式數列)
  6. base^exp (次方)
  7. base^exp ( O(logn) )
  8. gcd (最大公因數)


1. 1+2+...+n

規則:
f(n) = n + f(n-1) , for n > 0
f(n) = 0, for n <=0

int sum(int n)
{
    int i, sum=0;
    for(i=0; i!=n; ++i) sum+=i;
    return sum;
}

int sumr(int n)
{
    return (n<=0)?0:( n+sumr(n-1) );
}

 

2. 1-2+3-4+....+n

規則:
f(n) =  n + f(n-1), for n>0 and n is odd
f(n) =  -n + f(n-1), for n>0 and n  is even
f(n) = 0, for n <=0

int sum(int n)
{
    int i, sum=0;
    if(n<=0) return 0;
    for(i=0; i<=n; ++i) {
       sum+= (i&1) ? i : -i;
    }
    return sum;
}

int sumr(int n)
{
    // return (n<=0)?0:(sumr(n-1) + ((n&1) ? n : -n));
    if(n<=0) return 0;
    return sum(n-1) + (n&1 ? n : -n);
}

 

3. 1+4+9+16+....+n*n 

規則:
f(n) = n*n + f(n-1), for n>0
f(n) = 0, for n<=0

int sum(int n)
{
    int i, sum=0;
    if(n<=0) return 0;
    for(i=0; i<=n; ++i) {
       sum+=i*i;
    }
    return sum;
}

int sumr(int n)
{
    return (n<=0) ? 0 : (n*n+sumr(n-1));
}

 


4. n!  ( 階層函式)

規則:
f(n) = n*f(n-1), for n >0
f(n) = 1, for n<=0

int fact(int n)
{
    register int i=0, ans=1;
    if(n<=0) return 1;
    for(i=1; i<=n; ++i) ans*=i;
    return ans;
}

int factr(int n)
{
    return n<=0 ? 1 : n*factr(n-1);
}

 


5. fib (費式數列)

規則:
f(n) = f(n-1) + f(n-2)
f(0) = f(1) = 1
f(n) = 0, for n < 0

int fib(int n)
{
    register int i=0, a0=1, a1=1, a2=1, a3=2;
    if(n<0) return 0;
    if(n<=2) return n;
    for(i=1; i<n; ++i){
       a3 = a1+a2;
       a1 = a2;
       a2 = a3;
    }
    return a3;
}

int fibr(int n)
{
    if(n<0) return 0;
    return (n==0 || n==1) ? 1 : ( fibr(n-1) + fibr(n-2) );
}

 


6. base^exp (次方, O(n) )

規則:
f(base, exp) = base*f(base, exp-1), for exp>0
f(base, 0)  = 1
f(base, exp) = 0, for exp < 0

int power(int base, int exp)
{
    register int i=0, ans=1;
    if(exp<0) return 0;
    for(i=1; i<=exp; ++i){
       ans*=base;
    }
    return ans;
}

int powerr(int base, int exp)
{
    if(exp<0) return 0;
    return (base==0) ? 1 : (base*powerr(base,exp-1));
}

 

7  base^exp ( O(logn) )

規則:
f(base, 0)     = 1
f(base, exp) = 0, for exp < 0
f(base, exp) = base*f(base, exp/2)*f(base, exp/2), for exp>0 and exp is odd
f(base, exp) =           f(base, exp/2))*f(base, exp/2), for exp>0 and exp is even

int power_fast(int base, int exp)
{
    register int ans=1;
    if(exp<0) return 0;
    while(exp>=1){
       if(exp&1) ans*=base;
       exp>>=1;
       base*=base;
    }
    return ans;
}

int power_fastr(int base, int exp)
{
    register int tmp;
    if(exp<0) return 0;
    if(exp==0) return 1;
    tmp = power_fastr(base, exp>>1);

    if(exp & 1) return base*tmp*tmp;
    else return tmp*tmp;
}


 

8. gcd(p,q) (最大公因數)

規則:
gcd(p,q) = gcd(q, p%q), if p%q!=0
gcd(p,q) = q, if p%q=0

int gcd(int p, int q)
{
    register int tmp;
    while(p%q!=0){
       tmp = q;
       q = p%q;
       p = tmp;
    }
    return q;
}

int gcdr(int p, int q)
{
    if(p%q!=0) return gcdr(q, p%q);
    else return q;
}

 

edisonx 發表在 痞客邦 PIXNET 留言(0) 人氣()