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. baseexp (次方)
  7. baseexp ( 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. baseexp (次方, 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  baseexp ( 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;
}