Являются ли рекурсивные функции частным случаем функций более высокого порядка

Представьте, что ваш диалект Алгола не поддерживает рекурсию, но поддерживает функции более высокого порядка. Можем ли мы еще реализовать ваш пример? Что вы можете!

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. В остальном это совершенно разные вещи.

No.

выводит функцию означает, что функции могут использоваться в качестве возвращаемого значения функции, например так (код на Lua):

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

В вашем примере рекурсивной функции возвращаемое значение является результатом выражения foo(++i), а не самой функции foo.

Нет. «Вывод» функции в этом контексте означает возврат функции, а не результат вызова функции. То есть возвращаемое значение само по себе является вызываемым. Рекурсивные функции вообще не обязательно делают это. Например:

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

Этот код возвращает целое число. Вы не можете вызвать целое число, поэтому это не функция высшего порядка.