C語言: 遞迴用法

一個會呼叫自己本身的函數稱為遞迴(Resursive)。在實作遞迴函數時，最重要的一點就是必須有一個結束點的判斷。

如n階層，很適合用遞迴來實作

n! = n * (n - 1)!
(n - 1)! = (n - 1) * (n - 2)!
(n - 2)! = (n - 2) * (n - 3)!
:
:
1! = 1

以遞迴方式來實作n階層

#include <stdio.h>
#include <stdlib.h>

long Factorial(long n)
{
 if (n == 0 || n == 1)
  return 1;
 else
  return n * Factorial(n - 1);
}

int main(int argc, char *argv[]) {
 int i = 0;
 
 for (i = 1; i <= 10; i++)
  printf("Factorial(%2d) = %d\n", i, Factorial(i));
  
 return 0;
}

執行結果

fact( 1) = 1
fact( 2) = 2
fact( 3) = 6
fact( 4) = 24
fact( 5) = 120
fact( 6) = 720
fact( 7) = 5040
fact( 8) = 40320
fact( 9) = 362880
fact(10) = 3628800

以非迴圈方式來實作n階層

#include <stdio.h>
#include <stdlib.h>

long Factorial(long n)
{
 int i = 0;
 long sum = 1;
 
 if (n == 0 || n == 1)
  return 1;
 else
  for (i = 2; i <= n; i ++)
   sum *= i;
 return sum;
}

int main(int argc, char *argv[]) {
 int i = 0;
 
 for (i = 1; i <= 10; i++)
  printf("Factorial(%2d) = %d\n", i, Factorial(i));
  
 return 0;
}

執行結果

fact( 1) = 1
fact( 2) = 2
fact( 3) = 6
fact( 4) = 24
fact( 5) = 120
fact( 6) = 720
fact( 7) = 5040
fact( 8) = 40320
fact( 9) = 362880
fact(10) = 3628800

1. 在實作遞迴程式時，如果結束點定義錯誤，有可能造成stack overflow的情況發生。
2. 遞迴使用很多空間來存放暫時的結果，程式看起來比迴圈的方式簡單，但執行時間會花更多時間。