其實這個應該放在[Day3] 方法,那是什麼能吃嗎這篇文章裡
只是之前忘了提
加上本篇例子剛好會提到就把他拉出來講了
遞迴就是自己呼叫自己
這麼說有點抽象
讓我們看看範例程式碼
我想做一個加法器
輸入一個數字n
就會從1加到n
1+2+3+...+n
using System;
namespace Practice
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine(Sum(5)); //15
}
public static int Sum(int n)
{
if (n == 1)
{
return 1;
}
else
{
return n + Sum(n - 1);
}
}
}
}
讓我們把重點放在Sum()方法
如果n==1的時候 就回傳1
我們把這個稱作遞迴終止式
少了這行就會導致無窮迴圈的發生
上面google的圖 就是少了終止式
所以他會無限的問你是不是要找遞迴
那麼當n>1時
會回傳n + Sum(n-1);
以我們main例子中n代5進去
程式執行第一次時會是
會返回 5 + Sum(4);
但是Sum(4)又能拆成
4 + Sum(3)
依此類推
Sum(3) = 3 + Sum(2);
Sum(2) = 2 + Sum(1);
當遇到Sum(1)的時候
因為n == 1 所以會返還1
這時候
Sum(2) = 2 + 1 = 3
Sum(3) = 3 + Sum(2) = 3 + 3 = 6
Sum(4) = 4 + Sum(3) = 4 + 6 = 10
Sum(5) = 5 + Sum(4) = 5 + 10 = 15
也就是上底加下底乘以高除2
1+2+3+...+n = n * (n+1) / 2
小孩子才在那邊跟你一個一個算
但是在高斯發現這個方法前 人們還真的一個一個算
這也是演算法(algorithm)這門學科的重要性
降低問題的複雜度
能用簡單的方法當然還是使用簡單的
這個只是因為要用遞迴的範例才舉出來
後面會有有關階層計算的遞迴式
在數學上能用遞迴(recursion)寫的一定能夠改寫成用迭代(iteration,也就是for,while 迴圈)寫
反之亦然
但是遞迴的概念在Dynamic Programming 中是相當重要的
所以還是要了解他是如何運作的
介紹了遞迴
所以來試著用遞迴寫出費伯納契係數吧
公元1150年印度數學家Gopala和金月在研究箱子包裝物件長寬剛好為1和2的可行方法數目時,首先描述這個數列。在西方,最先研究這個數列的人是比薩的李奧納多(義大利人斐波那契Leonardo Fibonacci),他描述兔子生長的數目時用上了這數列:
我把程式碼放在https://github.com/peace920902/Fibonacci
在C#的語言裡面
主要能分成3種錯誤
通常是語法的錯誤
例如句尾忘記加分號
方法的名稱拼錯
忘記引用命名空間等等
通常這類錯誤編譯器會幫你將錯誤抓出來
用紅線指出你錯誤的地方
將滑鼠移至紅線上
能夠看見你哪裡錯誤
如圖 Console類別下面沒有writeLine的方法(因為w是小寫)
這時候將滑鼠移到燈泡上面
他同常會給你一些解決方案
這邊是沒有引用命名空間
console這個類別是在命名空間System下面的
通常是執行時期發生的錯誤
通常程式會拋出例外導致無法執行
這種情況就需要用本篇要講的try catch來處理
舉例來說常見的
除以0的錯誤
int a = 5 / 0;
轉型錯誤(前幾篇介紹 int.Parse() 如果轉型的東西是英文字母之類的就會報錯)
out of index 你取的值超過陣列索引
int[] arr = new int [3]{0,1,2}; //宣告一個長度為3的整數陣列
Console.WriteLine(arr[3]) // 拋出例外 陣列索引從0開始 所以只存在arr[0],arr[1],arr[2]
null reference的錯誤等等
Car MyCar;
MyCar.GO(); // 因為沒有指派空間給MyCar放 所以MyCar的標標指向null 自然找不到MyCar.GO 的方法
關於這個例子可參考下昨天的文章[Day4] 我知道Class 班級對吧
這個錯誤不會造成任何的例外
單純是在撰寫程式時因為思考不週導致程式的執行結果不如預期
比較常見的例子是無窮迴圈
或是OR(||)跟AND(&&)搞錯
舉個例子
這是在問答區的一篇文章
雖然是使用C寫的
C語言 遞迴
讓我用C#改寫下
using System;
namespace Practice
{
class Program
{
static void Main(string[] args)
{
int x = 200;
Console.Write(Factorial(200));
}
public static int Factorial(int n)
{
return n * Factorial(n - 1);
}
}
}
這個例子裡他犯了2個錯誤
一個是沒有設定終止條件式
我們以n = 2為例
Factorial(2) = 2 * Factorial(1) = 2 * 1 * Factorial(0) = 2 * 1 * 0 * Factorial(-1)......
如此無窮進行下去
這就是我們所稱的邏輯錯誤
應改改寫為
public static int Factorial(int n)
{
if(n == 1)
{
return 1;
}
return n * Factorial(n - 1);
}
另一個錯誤是
原文中它想要求200!
但是函式的返回值為int
還記得我們在[DAY2] 現在讓我們正式進入C#的世界吧 中所提的資料型別嗎
int 最多能存放的值為 +2147483647
200!大概有多大呢
我無法想像
不只是我 Google也無法想像(其實可以 只是這個計算機沒算出來)
光是13! 就有 6227020800 超過 int 的上限了
因此就算他記得加上遞迴終止式
也會因為int 塞不下導致執行錯誤
這邊所能處裡的只有執行錯誤
編譯錯誤根本不讓你跑
邏輯錯誤 只能一行一行看了
(關於debug技巧 之後可能會發一篇文章介紹)
先來看看怎麼使用吧
try{
//你的程式碼
}
catch(Expection e){
//這段程式碼的錯誤處理
}
來看個範例
static void Main(string[] args)
{
try
{
string tw = "台灣";
Console.WriteLine(int.Parse(tw));
}
catch (Exception e)
{
Console.WriteLine("轉型失敗");
}
}
因為"台灣"不能轉型成數字
所以會拋出錯誤
這個錯誤會被
Exception所接住
並執行錯誤處理
原則上excpetion 所接住的的是所有的意外
如果我今天想要對應不同的意外作處理
那麼
catch 中的 exception 就要對應到該例外的名稱
例如上述範例為FormatException
那麼我們改寫下程式碼
using System;
namespace Practice
{
class Program
{
static void Main(string[] args)
{
try
{
string tw = "台灣";
Console.WriteLine(int.Parse(tw));
}
catch (FormatException ex)
{
Console.WriteLine("台灣轉型失敗");
}
catch (Exception e)
{
Console.WriteLine("發生其他例外");
}
}
}
}
//台灣轉型失敗
注意
catch (FormatException ex)要放在catch (Exception e)前面
不然例外會先被catch (Exception e)捕捉
寫這篇之後覺得應該要把他跟[Day4] 互換
原則上基礎語法的部分到這邊