Хвостовая "рекурсия" и взаимная хвостовая "рекурсия" на C

Хвостовая рекурсия — специальный случай рекурсии, при котором рекурсивный вызов функцией самой себя является её последней операцией.^[1] Подобный вид рекурсии примечателен тем, что может быть легко заменён на итерацию, что реализовано во многих оптимизирующих компиляторах.

Википедия

К сожалению, в таком языке как C, по стандарту, данная возможность является не положенной, в связи с чем, рекурсия останется как есть, и скушает много памяти. Ниже приведён код, в котором описывается небольшой набор типов данных и функций для того, что бы реализовать некоторое подобие хвостовой рекурсии ручками.

typedef struct ReturnValue (* RecurFunction) (void *);

struct ReturnValue {
  RecurFunction function;
  void * value;
};

void * recur(RecurFunction function, void * input) {
  struct ReturnValue tmp;
  tmp.value = input;
  tmp.function = function;
  do {
    tmp = tmp.function(tmp.value);
  } while (tmp.function != NULL);
  return tmp.value;
}

Основная идея этого решения следующая: функция во время своего вычисления, формирует структуру данных типа ReturnValue, в которой определяется в поле value результат вычисления или задаётся функция, которая должна быть вычислена в следующую "итерацию" и её аргументы. Ограничения и неудобства решения видны сразу, рекурсивная функция должна быть типа RecurFunction, на вход получать void* (а значит и преобразовывать типы), и её результат должен быть представлен типом ReturnValue. Это делает код довольно страшным...
Посмотрим на классический пример, а именно на вычисление факториала:

// Тип входных данных.
struct RecurFactorial {
  int n, acc;
};
struct ReturnValue factorial(void * input) {
  struct RecurFactorial * args = input; // Приведение типа данных.
  struct ReturnValue result;
  result.value = input; // Входные и результируещие данный одни и теже.
  if (args->n == 1) {
    // Функция на следующий запуск не устанавливается для завершения вычислений.
    result.function = NULL;
  } else {
    // Формируем результаты итерации.
    args->acc *= args->n;
    args->n -= 1;
    // Устанвливаем функцию на следующий запуск.
    result.function = factorial;
  }
  return result;
}

Теперь рассмотрим пример поинтереснее, с двумя взаимно-рекурсивными функциями. Реализуется алгоритм с примерно тем же поведением (и с ошибкой на списке нулевой длинны), что у кода на Haskell в этом посте про алгоритм определения конца списка.

struct RecurLoopInList {
  struct List * fastMarker, * slowMarker;
};

struct ReturnValue slowMarker(void * input);
struct ReturnValue fastMarker(void * input);

bool loopInList(struct List *head) {
  struct RecurLoopInList args;
  args.fastMarker = head->next;
  args.slowMarker = head;
  bool * resultP = recur(fastMarker, (void*)&args);
  bool result = *resultP;
  free(resultP);
  return result;
}

struct ReturnValue slowMarker(void * input) {
  struct RecurLoopInList * args = input;
  struct ReturnValue result;
  result.value = input;
  args->slowMarker = args->slowMarker->next;
  result.function = fastMarker;
  return result;
}

struct ReturnValue fastMarker(void * input) {
  struct RecurLoopInList * args = input;
  struct ReturnValue result;
  if (args->fastMarker->next == NULL ||
      args->fastMarker->next->next == NULL) {
    bool * ans = malloc(sizeof(bool));
    *ans = false;
    result.value = (void*)ans;
    result.function = NULL;
  } else if (args->fastMarker->next == args->slowMarker ||
             args->fastMarker->next->next == args->slowMarker) {
    bool * ans = malloc(sizeof(bool));
    *ans = true;
    result.value = (void*)ans;
    result.function = NULL;
  } else {
    args->fastMarker = args->fastMarker->next->next;
    result.value = (void*)input;
    result.function = slowMarker;
  }
  return result;
}

Целиком весь код можно увидеть тут: https://gist.github.com/1003337

PS. есть ли другой подход, что бы сделать взаимно-рекурсивные функции на C без стека и платформо-независимо?

Один хороший человек с ником Powerfox предложил решение через контексты.

Проверка списка на наличие цикла в O(1) по памяти

Есть произвольный односвязный список, в котором может быть петля, необходимо предложить алгоритм который бы позволил определить, есть ли цикл в O(1) по памяти.

Не то, что бы эта задача была сложной, но она по своему довольно интересна. Ниже приведено два подхода к решению этой задачки. Первое из них является классическим решением, второй подход пораждён мои больным сознанием по мотивам решения задачки по Обходу бинарного дерева с константным количеством памяти.

Подход правильный.
При анализе того, как решить эту задачу очень быстро приходишь к мысли, что необходимо где-то в списке оставить маркер, который позволит понять, что мы в этом узле уже были. Очень быстро становится очевидно, что нет никакой возможности оставить маркер гарантированно на одном из улов петли. Решить эту проблему можно следующим образом: пустить по систем в параллель несколько маркеров с разной скоростью. Таким образом, более быстрый маркер должен дойти дойти либо до конца списка, либо рано или поздно догнать медленный маркер.

Реализация на С:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct List {
  struct List *next;
  int value;
};

struct List* makeList(int all, int inLoop) {
  struct List *head = malloc(sizeof(struct List));
  struct List *current = head;
  int marker = 1;
  for (int i = 0; i < all - inLoop; ++i) {
    current = current->next = malloc(sizeof(struct List));
    current->value = marker++;
  }
  if (inLoop > 0) {
    struct List *loopStart = current;
    for (int i = 0; i < inLoop; ++i) {
      current = current->next = malloc(sizeof(struct List));
      current->value = marker++;
    }
    current->next = loopStart->next;
  }
  return head;
}

bool loopInList(struct List *head) {
  struct List *fastMarker, *slowMarker;
  fastMarker = slowMarker = head;
  if (fastMarker->next == NULL) return true;
  else fastMarker = fastMarker->next;

  while (true) {
    if (fastMarker->next == NULL ||
        fastMarker->next->next == NULL)
      return false;
    if (fastMarker->next == slowMarker ||
        fastMarker->next->next == slowMarker)
      return true;
    fastMarker = fastMarker->next->next;
    slowMarker = slowMarker->next;
  }
}

int main(int argc, char** argv) {
  struct List * head = makeList(10, 0);
  printf("%s", loopInList(head) ? "true" : "false");
  return 0;
}

Реализация на Haskell. Собственно как и практически всегда у меня этим языком - первая мысль: "А как это вообще сделать?", вторая: "Так очевидно же как...".

makeList all inLoop = [1 .. (all - inLoop)] ++ loopListPart
    where loopListPart | inLoop > 0 = [(all - inLoop + 1) .. all] ++ loopListPart
                       | otherwise = []

list = makeList 5000000 500000

loopInList list@(x:xs) = fastMarker list xs
    where slowMarker (_:slows) fast = fastMarker slows fast
          fastMarker _ [] = False
          fastMarker _ (_:[]) = False
          fastMarker allSlow@(slow:_) (fast1:fast2:fasts)
              | fast1 == slow || fast2 == slow = True
              | otherwise = slowMarker allSlow fasts

main = putStrLn $ show $ loopInList list

Подход не правильный, но работающий.
Этот подход основывается на предпосылки - данные можно изменять. Идея следующая, проходим список вперёд разворачивая его. Если конец списка совпадёт с головой - значит была петля. Повторная проходка позволит восстановить исходную структуру данных. Реализация на C (только функция проверки):

bool loopInList(struct List *head) {
  struct List *current = head, *last = head, *next;
  current = last = head;
  if (current->next == NULL) return true;
  else {
    current = current->next;
    last->next = NULL;
  }
  while (current->next != NULL) {
    printf("%d ", current->value);
    next = current->next;
    current->next = last;
    last = current;
    current = next;
  }
  if (current == head) return true;
  else return false;
}