是遞歸函數的高階函數的特殊情況

在數學和計算機科學中，高階函數（也功能形式，功能或算符）的，做了功能以下中的至少一個：

採用一個或多個作爲輸入

輸出功能

此外，

遞歸函數是其執行過程中調用自身的功能。

這是否意味着遞歸函數可以歸類爲高階函數的一個非常特殊的情況？

請參考此情況下：

int foo(int i) 
{ 
    if(i>10) 
    { 
     return 10; 
    } 
    cout<<i; 
    return foo(++i); 
}

我不想意見。請說明您的答案與特定的場所。

來源

2014-11-05 Nilay Vishwakarma

什麼是我們可以選擇的其他分類？ – 2014-11-05 15:21:30

您在編輯中引用的功能不是「高級功能」。它將遞歸調用產生的**值**返回給它自己，而不是返回一個函數。分享並享受。 – 2014-11-05 15:30:01

想象一下，你的Algol方言不支持遞歸，但支持更高階的函數。我們能否仍然實施你的例子？你當然可以！

int foo_aux(int i, Func cont) 
{ 
    if(i>10) { 
     return 10; 
    } else { 
     cout<<i;     // side effect bad! 
     return cont(i+1, cont); // no recursion 
    } 
} 

int foo(int i) 
{ 
    return foo_aux(i, [] (int i, Func cont) -> int { return foo_aux(i,cont) }); 
}

想象一下，你嘗試做相同的，但你的語言不支持高階函數，也不遞歸。是否有可能模仿它？一切皆有可能：

std::stack<int> args;  // integers can be castable pointers or numbers! 
int cont = 2; 
while(cont) { 
    if(cont == 2) {   // main 
     args.push(1) 
     cont=1;    // continuation == foo_aux 
    } else if (cont == 1) { // foo_aux 
     int tmp = args.pop(); 
     if(tmp > 10) { 
      args.push(10); 
      cont=0;   // continuation == return/exit 
     } else { 
      cout << tmp; 
      args.push(tmp+1); 
      // not setting cont == recursion 
     } 
    } 
} 
// do something with the result 
return args.pop();

這是一種在您的初始示例中進行遞歸的方法。也許你可以讓一個預處理器（宏）做一些像你的例子一樣的轉換，然後轉換成編譯。如果您想將該功能作爲參數傳遞，您只需按下該號碼，您的接收功能就需要設置f。

std::stack<int> args;  // integers can be castable pointers or numbers! 
args.push(2)    // bootstrap 
int cont = 0; 
while(cont = args.pop()) { 
    if(cont == 2) {   // main/foo 
     args.push(1)    // push argument 
     args.push(1)    // push function 
    } else if (cont == 1) { // foo_aux 
     int tmp = args.pop(); 
     if(tmp > 10) { 
      args.push(10);  // push result 
      args.push(0);  // push exit as continuation 
     } else { 
      cout << tmp; 
      args.push(tmp+1); // push argument 
      args.push(1);  // push self as argument 
     } 
    } 
} 
// do something with the result 
return args.pop();

這並不支持所謂的向上funarg從那以後你就需要有其他構成範圍關閉了變量不再。

所以遞歸是一個高階函數的特例？由於可以使用函數索引來模擬函數，因此可以從編譯器視圖同時實現函數，遞歸和高階函數。這隻意味着功能可以用相同的方式建模。完全有可能使一個使用匯編函數的編譯器不支持更高階的函數，但支持遞歸，並且可以創建一個沒有遞歸的語言來支持更高階的函數，這將使得像Y combinator這樣的遞歸方法成爲可能。除此之外，它們是完全不同的東西。

來源

2014-11-05 20:26:34 Sylwester

Thnx。很好的總結 – 2014-11-05 20:29:08

在這種情況下，「輸出」一個函數意味着返回一個函數，而不是返回調用函數的結果。也就是說，返回值本身是可調用的。遞歸函數通常不一定這樣做。例如：

def factorial(n: int) -> int: 
    if n == 0: 
     return 1 
    else: 
     return n*factorial(n-1)

此代碼返回一個整數。你不能調用一個整數，所以它不是一個高階函數。

來源

2014-11-05 15:21:41 Kevin

號

輸出功能裝置功能可以用作函數的返回值，像這樣（在Lua代碼）：

function foo() 
    return function(a,b) return a + b end 
end

在您的遞歸函數的例子中，返回值是表達式foo(++i)的結果，而不是函數foo本身。

來源

2014-11-05 15:22:44

參考已編輯的問題 – 2014-11-05 15:26:24

您可以將lua代碼轉換爲c/C++/java/js。我無法在一個聲明中理解使用情況或兩個回報。 – 2014-11-05 15:30:00

我使用Lua是因爲它支持更高階的函數，即使您不知道它也很容易理解。關鍵在於'function（a，b）return a + b end'是函數定義的語法。 – 2014-11-05 15:32:42

是遞歸函數的高階函數的特殊情況

回答

相關問題