開放形式和封閉形式

Question

如何將開放形式的再發生轉換爲其等效封閉形式。 此外，通常有效使用的一些常用封閉表格是 。

Answer 1

我想你是在談論遞歸函數和數學。

例如考慮以下總和遞歸函數

sum(0) = 0 
sum(i) = sum(i-1) + i 

此表單未關閉。一個封閉的表格是sum(n) = (n+1)*n/2，其中您只使用基本操作，如+ - * /，功率，有時是階乘。

對於您的問題，如何將開放式公式轉換爲封閉形式。答案是沒有一般規則將所有開放形式轉換爲封閉形式，因爲一些開放形式沒有等價的封閉形式。

你可以參考Concrete Mathematics對這個問題的嚴肅處理。本書的主要目標是將大量遞歸函數/開放表單轉換爲封閉表單。

Answer 2

一個開放的形式通常是作爲一個方程來解決。例如，

a(0) = 1   -- base case 
a(n) = b * a(n-1) -- recurrence relation 

要將其轉換成封閉形式，你解決遞推關係。在這種情況下，重複進行置換，直至到達基準情況給你

a(n) = b * a(n-1) = b * b + a(n-2) = ... = b * b * ... * b * a(0) = b^n 

這是更有效的，因爲功率可以在對數時間來評價在Ñ（即正比於登錄Ñ）而原始遞歸關係在n需要時間線性。

有許多技術用於解決復發關係。一些示例可以在wikipedia article中找到。但重要的是要認識到並非所有的復發關係都可以解決，但實際上大多數解決不了（這就是編程很重要的原因！）