Является ли хвостовая рекурсия всегда быстрее, чем классическая рекурсия, и если да, то как мне исправить мой код? - PullRequest
Новая
       38

Является ли хвостовая рекурсия всегда быстрее, чем классическая рекурсия, и если да, то как мне исправить мой код?

0 голосов
/ 31 мая 2019

Я студент математики, но у меня также есть несколько курсов по программированию в этом году, и на одном из них мы используем C, чтобы изучить некоторые "базовые" методы программирования, одним из которых является рекурсия.Итак, я обнаружил, что хвостовая рекурсия в целом должна быть быстрее, чем классическая рекурсия из-за оптимизации компилятора gcc (думаю, очистка стека вызовов), и я попробовал в примере функцию, которая должна суммировать все элементы данного массива, и я рассчитал время,но я получаю намного лучшее время для регулярной рекурсии, чем хвост (или я просто недостаточно хорошо ее реализовал)

Сначала я подумал, что проблема связана с моей машиной (хе-хе), но когда я его попробовал2 других компьютера я это исключил.Я также попытался передать указатель на переменную, которая содержит возвращаемое значение, но это также не решило мою проблему.

Это код для хвостовой версии: 

long sum1(int arr[],int start,int len,long acom){
  if(start==len){
    return acom;
  }
  return sum1(arr,start+1,len,arr[start]+acom);
}

Это обычный код: 

long sum2(int arr[],int start,int len){
  if(start==len){
    return 0;
  }
  return (arr[start]+sum2(arr,start+1,len));
}

Вызовы функций: 

long s1=sum1(arr,0,len,0L);
long s2=sum2(arr,0,len);

Я ожидал, что s1 будет быстрее, но .. 

s1 = 0.000192 seconds
s2 = 0.000017 seconds

Также я использовал 

gcc sum.c -o sum -O3

дляпрограмма компиляции.

...