Edison.X. Blog

[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 (exp==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;
}