遞歸通常很直白地描述了一個求解過程，因此也是最容易被想到和實現的算法。循環其實和遞歸具有相同的特性（即：做重復任務），但有時，使用循環的算法并不會那么清晰地描述解決問題步驟。單從算法設計上看，遞歸和循環并無優劣之別。然而，在實際開發中，因為函數調用的開銷，遞歸常常會帶來性能問題，特別是在求解規模不確定的情況下。而循環因為沒有函數調用開銷，所以效率會比遞歸高。除少數編程語言對遞歸進行了優化外，大部分語言在實現遞歸算法時還是十分笨拙，由此帶來了如何將遞歸算法轉換為循環算法的問題。算法轉換應當建立在對求解過程充分理解的基礎上，有時甚至需要另辟蹊徑。
前段時間遇到過這樣的問題：已知一2D地圖格子的長寬（w、h）及每個格子的邊長（a，格子為正方形），給定物體的2D坐標（pos[x , y]）及半徑（r），求解物體在2D地圖格子中所占的格子，僅考慮n*n的情況。大概的求解過程如下：
1）根據半徑，確定n*n中的n。假定計算公式為：n = Round(2*r / a)
2）根據2D坐標得到物體的“中心格子”。根據n的奇偶，計算公式不同，如下圖所示。
n為偶數[1] n為奇數[2]
[1]：grid(x , y) = Round(pos / a)
[2]：grid(x , y) = Floor(pos / a)
其中，格子坐標x >= 0 , y >= 0。
3）以“中心格子”為基礎，求出物體占據的其他格子。這樣的描述，讓人容易想到遞歸，就像用深度優先方法遍歷樹那樣，偽代碼算法如下：
if n is even
{
get the index of 'center grid' (row , col)
ExtendHeldGrid(row , col , n)
ExtendHeldGrid(row - 1 , col , n)
ExtendHeldGrid(row - 1 , col - 1 , n)
ExtendHeldGrid(row , col - 1 , n)
}
else
{
get the index of 'center grid' (row , col)
ExtendHeldGrid(row , col , n)
}
function ExtendHeldGrid(row , col , level)
{
if(level <= 0)
return
if((row >= 0 and row < MaxGridWidth) and (col >= 0 and col < MaxGridHeight))
{
mark the grid(row , col)
ExtendHeldGrid(row , col , level - 2)
if(level - 2 > 0)
{
ExtendHeldGrid(row + 1 , col , level - 2)
ExtendHeldGrid(row - 1 , col , level - 2)
ExtendHeldGrid(row , col + 1 , level - 2)
ExtendHeldGrid(row , col - 1 , level - 2)
ExtendHeldGrid(row + 1 , col + 1 , level - 2)
ExtendHeldGrid(row - 1 , col + 1 , level - 2)
ExtendHeldGrid(row + 1 , col - 1 , level - 2)
ExtendHeldGrid(row - 1 , col - 1 , level - 2)
}
}
}
雖然，該算法得到了正確的求解結果，但是由于每個格子都會標記周圍的8個格子，所以存在大量的重復，再者如果上面的過程每幀都進行的話，函數調用開銷也是相當可觀。
循環自然是不可避免的，消除重復便成了優化的目標。分析格子圖和n為2和3的情況，試圖找出用循環代替遞歸的方法，我發現了下面一個有趣的規律：
從“中心格子”出發，順時針（或逆時針）以上圖方式可以走遍所求解的每個格子而不重復。在實現上，每個轉角也是有規律的，可以通過一個2*2的轉角矩陣來控制：
[1 , 0][0 , -1]
[0 , 1][-1 , 0]
順時針方式的轉角陣
矩陣中的每個元素代表從當前格子走到下個格子在row和col上的變化。加之，在轉角之間的路長（以格子個數計）有每轉兩次遞增單位1的規律，算法就不難得到了，下面同樣以偽代碼示：
conerMat =
{
{0 , -1} ,
{-1 , 0} ,
{0 , 1} ,
{1 , 0}
}
dir = 0 /// 轉角控制，四個轉角順時針0~3
span = 1 /// 轉角間的跨度
count = 1 /// 每兩次增加一個跨度
rin = 1 /// 下一個轉角的循環索引
if n is even
get the index of 'center grid' (row , col)
else
get the index of 'center grid' (row , col)
for(i = 0; i < n * n; ++i)
{
if((row >= 0 and row < MaxGridWidth) and (col >= 0 and col < MaxGridHeight))
mark the grid(row , col)
if(i == rin)
{
dir = (dir + 1) % 4
if(count == 2)
{
++span
count = 1
}
else
++count
rin = i + span
}
row = row + conerMat[dir][0]
col = col + conerMat[dir][1]
}
用MFC程序驗證了一下算法的正確性，標號展示了循環的路線（注意GDI的坐標系中Y的正方向朝下）：
