[資料結構(Data Structure, DS)] 基礎遞迴

階乘演算法

• 用遞迴設計階乘演算法
  • 階乘(Factorial)： n! = 1 × 2 × 3 × ... × (n-1) × n;
  • 設計遞迴
    • Base Case：if n = 0 return 1
    • General Case：if n > 0 return n × Factorial(n-1)
  • 演算法
    • C++
    • C
    • C#
    • Java

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

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

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

    int Factorial(int n)
    {
        if( n == 0)
            return 1;
        else
            return n * Factorial(n - 1);
    }
    
  • 問題：若執行Factorial(3)，會呼叫Factorial( )幾次?
    • 
    • ∴共4次
  • 問題：若執行Factorial(n)，會呼叫Factorial( )幾次?
    • 執行執行Factorial(n)，會呼叫Factorial( )共n+1次