資料結構第三章小考參考解答
        課本： Data Structures Using C and C++
           by Y. Langsam, M. J. Augenstein and A. M.Tenenbaum

3.1.3(c)  Let a be an array of integers. Write a recursive C function
   to compute the sum of the elements of the array.
   
Solution :
   int sum(int a[], int size) //size is the number of elements in array a[]
   {
        if(size == 0)  // no element
          return 0;
        else
          return a[size-1] + sum(a, size - 1);
   }


3.1.3(e)  Let a be an array of integers. Write a recursive C function
   to compute the average of the elements of the array.
   
Solution :
   float avg(int a[], int size) //size is the number of elements in array a[]
   {
        if(size == 0)  // no element
          return 0;
        else
          return (a[size-1] + avg(a, size - 1)*(size -1))/size ;
   }


3.2.2  The C expression m % n yields the remainder of m upon division by n.
   Write a recursive C function to find the greatest common divisor (GCD)
   of two integers.

Solution:
   int gcd(int m, int n)
   {
        if(m < n)
                return gcd(n, m)
        else if(n == 0)
                return m;
        else
                return gcd(n, m % n);
   }

3.1.8  （改寫過）
  The Fibonacci sequence is defined recursively:
        f(n) = n if n == 0 or n == 1
        f(n) = f(n - 2) + f(n - 1) if n >= 2
  (a)Suppose we use an iterative method to compute f(n).
     How many additions are required ? (15%)
  (b)Suppose our program is written recursively for computing f(n).
     How many additions are required ? Please drerive a general pattern.(25%)
     
Solution:
(a)iterative : 
        f(0) = 0   加法 0 次
        f(1) = 1   加法 0 次
        f(2) = f(1) + f(0)   加法 1 次
        f(3) = f(2) + f(1)   加法 2 次
        ...
        令 g(n) 為計算 f(n) 所需加法次數，從以上推論得知：
        g(n)=0 , 當 n = 0 or 1 時
        g(n)=g(n-1)+1  當 n >= 2 時
        展開可得 g(n)=n-1  當 n >= 2 時
        所以 f(n) 需要加法  0  次, 當 n = 0 or 1 時
             f(n) 需要加法 (n-1) 次, 當 n >= 2 時

(b)recursive :
        f(0) = 0   加法 0 次
        f(1) = 1   加法 0 次
        f(2) = f(1) + f(0) 需要 f(1)、f(0)與這式子本身的加號, 故需要加法1 次
        f(3) = f(2) + f(1) 需要 f(2)、f(1)與這式子本身的加號, 故需要加法2 次
        f(4) = f(3) + f(2) 需要 f(3)、f(2)與這式子本身的加號, 故需要加法4 次
        f(5) = f(4) + f(3) 需要 f(4)、f(3)與這式子本身的加號, 故需要加法7 次
        ...
        令 g(n) 為計算 f(n) 所需加法次數，從以上推論得知：
        g(n)=0 , 當 n = 0 or 1 時
        g(n)=g(n-1)+g(n-2)+1  當 n >= 2 時
        --------------------------------------------
        另解：
           由f(n)之定義得知：
           f(0)=0,  f(1)=1,  f(2)=1,  f(3)=2,  f(4)=3, f(5)=5, f(6)=8
           由觀察得知：
              g(n)=f(n+1)-1, 當 n >= 2 時
           利用數學歸納法證明：
              g(2)=f(3)-1=2-1=1
              假設 n=k 成立， 即 g(k)=f(k+1)-1
              證明 n=k+1之情形：
                   g(k+1)=g(k)+g(k-1)
                         =[f(k+1)-1]+[f(k)-1]+1
                         =f(k+1)+f(k)-1
                         =f(k+2)-1