递归函数是高阶函数的特例吗？

Question

维基百科说：

在数学和计算机科学中，高阶函数(也是函数式、函数式或函数式)是至少执行下列某一项的函数：

• 接受一个或多个函数作为输入。
• 输出函数

另外，

递归函数是在执行过程中调用自己的函数。

这是否意味着递归函数可以被归类为高阶函数的非常特殊的情况？

请将此案件转介：

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

我不想要意见。请用具体的前提说明你的回答。

Answer 1

假设您的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();

这不支持所谓的向上漏斗，因为那时您需要为封闭的变量提供另一个结构，不再适用于范围内的变量。

那么递归是高阶函数的特例吗？由于可以使用函数索引来模拟函数，所以可以从编译器的角度同时实现函数、递归和高阶函数。这只意味着函数可以以同样的方式建模。完全有可能使编译器使用不支持高阶函数但支持递归的汇编函数，并且可以生成一种无需递归的语言，该语言支持高阶函数，从而支持使用类似于Y组合子的方法进行递归。除此之外，他们是完全不同的东西。

Answer 2

不是的。此上下文中的“输出”函数意味着返回函数，而不是返回调用函数的结果。也就是说，返回值本身是可调用的。递归函数一般不一定做到这一点。例如：

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

此代码返回一个整数。你不能调用一个整数，所以它不是一个高阶函数.

Answer 3

不是的。

输出函数意味着函数可以用作函数的返回值，如下所示(Lua中的代码)：

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

在递归函数的示例中，返回值是表达式foo(++i)的结果，而不是函数foo本身的结果。