Are recursive functions a special case of higher order functions

Question

Wikipedia states:

In mathematics and computer science, a higher-order function (also functional form, functional or functor) is a function that does at least one of the following:

• takes one or more functions as an input
• outputs a function

Also,

A recursive function is a function that calls itself during its execution.

Does this mean a recursive function could be classified as a very special case of higher-order function?

Please refer this case:

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

I do not want opinions. Please state your answer with specific premises.

Answer 1

Imagine your Algol dialect didn't support recursion but supported higher order functions. Could we implement your example still? Sure you can!

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) });
}

Imagine you try to do the same but your language doesn't support higher order functions nor recursion. Is it possible to emulate it? Everything is possible:

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();

This is a way of doing recursion like in your initial example. Perhaps you could make a preprocessor (macro) to do the conversion from something fancy like your example to become this for compilation. If you wanted to pass the function as an argument you just push the number and your receiving function would need to set 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();

This does not support so called upwards funarg since then you need to have another structure for closed over variable no longer in scope.

So is recursion a special case of higher order functions? Since functions can be emulated using a function index it's possible to implement functions, recursion and higher order functions at the same time from a compiler view point. This only means functions can be modeled the same way. It's perfectly possible to make a compiler that uses assembly functions that do not support higher order functions but support recursion and it's possible to make a language without recursion that support higher order functions that will enable a way of doing recursion with something like a Y combinator. Other than that they are completely different things.