Рекурсивные функции

Конечно, можно вот так:

int fact_rec2(int n)
{
    if(n<1) return 0;
    if(n==1) return 1;
    return n*fact_rec2(n-1);
}

Ето я понимаю. Вопрос в том, почему функция правильно вычисляет результат, если пользоватся вспомогательной переменной, не возвращая её через return? Баг или фича?

Переменная разместилась в регистре/памяти, который по ABI является местом возврата параметра типа int (eax для x86).

На другой архитектуре/компиляторе все сломается.

То есть, ето что-то типа задачи «сколько будет i++ + ++i»? :)

man стек. То, что считает правильно - случайность.

Результат сильно зависит от опций оптимизации. Нормальный компилятор в режиме приличной оптимизации автоматически обнаруживает что a можно не вычислять - оно же далее не используется. Как следствие приходится оставить только пару if и вызов (хотя и он может быть соптимизирован, т.к. побочного эффекта нет). Кроме того нормальный компилятор (правда, возможно, для этого потребуются дополнилеьные опции типа -Wall) сообщит, что программист чего-то не доделал.

В принципе в обратном случае, т.е. при отсутствии оптимизации, наборот регистры могут быть использованы безобразно плохо, и регистр возврата может быть засран чем угодно.

Т.ч. данный результат может быть обусловлен только абсолютным везением.

То есть, ето что-то типа задачи «сколько будет i++ + ++i»? :)

Да, типа того.

abr_linux

return a;//почему эту строчку можно не писать?

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

io

Т.ч. данный результат может быть обусловлен только абсолютным везением.

не, на x86 этот быдлокод «всегда» работает. Что совсем не отменяет того факта, что это быдлокод, который в любой момент может сломаться.

не, на x86 этот быдлокод «всегда» работает.

Без return a; ? У меня не работает.

Вернее так: работает только без оптимизации, т.е. gcc -O0 ...

Вот именно, -O1 уже хватает!!

$ gcc -o fact fact.c -O1
$ for i in $(seq 1 10); do echo $i | ./fact; done
1
1
1
1
1
1
1
1
1
1

Или я просто туплю?

Действительно, тупишь.

return 1;
return 0; //почему эту строчку можно не писать?

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

1. возможно быстрее считать на FPU.
2. это хвостовая рекурсия, её можно заменить циклом. Естественно неявный return при этом сломается.

Macil

Ибо, оптимизация хвостовой рекурсии не есть фишка языка.

разве gcc этого не умеет?

разве gcc этого не умеет?

Я не знаю. Может быть и умеет. Но компилятор X это не умеет. И не должен уметь.

А вообще - интересно. Неужели GCC идет слинкованным с libastral?

не успеваю за полётом вашей мысли.

Причем тут libastral? gcc, вроде как умеет хвостовые рекурсии заменять. Как - уже вопрос к разработчикам.

разве gcc этого не умеет?

Важна взаимная рекурсия, а также всякие хитрые продолжения. Там во всю используется оптимизация хвостового вызова. Сильно сомневаюсь, что такое когда-нибудь будет реализовано в Си++, ибо не стоит оно того. Это совсем не ниша Си++.

К примеру, в .NET для обозначения хвостового вызова в байт-коде должна быть прописана особая инструкция. Насколько понимаю, компилятор C# не умеет делать хвостовые вызовы, а вот компилятор F# во всю их использует, помечая чуть ли не каждый вызов метода как потенциально хвостовой, что несколько замедляет исполнение. Думаю, что разработчики компиляторов Си++ здесь никогда не пойдут по пути F#. То есть, ответ отрицательный.

Есть еще оптимизация, когда хвостовой вызов внутри одной функции заменяется циклом. Это - лишь частный случай оптимизации хвостового вызова. Такое умеют даже Scala c clojure, тогда как в самой JVM нет вовсе поддержки хвостовой рекурсии. Многие почему-то путают и считают, что это и есть вся оптимизация хвостового вызова... Вероятно, gcc что-то подобное умеет.

dave

Важна взаимная рекурсия, а также всякие хитрые продолжения.

то, что компилятор не всё может оптимизировать - и так понятно. Но у нас тут случай очень простой, и оптимизация очевидна.

dave

Думаю, что разработчики компиляторов Си++ здесь никогда не пойдут по пути F#. То есть, ответ отрицательный.

Во первых мы про C. Во вторых - не думаю, что реализация какого-то C# (ещё и закрытая!) как-то повлияла на разрабов gcc.

dave

Есть еще оптимизация, когда хвостовой вызов внутри одной функции заменяется циклом

у нас именно тот случай.

dave

Такое умеют даже Scala c clojure

ещё-бы. У них циклы-то есть? А что они их не юзают?

dave

Многие почему-то путают и считают, что это и есть вся оптимизация хвостового вызова...

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

Во первых мы про C. Во вторых - не думаю, что реализация какого-то C# (ещё и закрытая!) как-то повлияла на разрабов gcc.

исходники F# открыты

https://github.com/fsharp

не умеет

Эта функция не вычисляет факториал, потому что 0! == 1, а не 0.

Macil

Действительно, тупишь

не-не, посмотри внимательно, поток исполнения вполне может достичь return a, и он в этом случае имеет смысл и обязан там находиться

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

Однако, продолжения используются во всю (F# async). И я совершенно не представляю, как их реализовать на Си или Си++. Тут столько ограничений платформы (которая, якобы чуть ли не «портабельный ассемблер»).

Возвращаясь к нашим баранам. Можно запросто проверить gcc, скормив ей функцию факториала. Только последнюю надо переписать через аккумулятор и хвостовой вызов, а также заюзав биг нумберс.

Хотя биг нумберс все равно не помогут. Лучше уж на Фибоначчи тестировать.

Reset

исходники F# открыты

а исходники оригинального компилятора C#?

Reset

не умеет

пруф?

Да, был не прав, похоже научили уже.

$ ulimit -s 1
$ cat 10.c
#include <stdio.h>
#include <stdint.h>

uint64_t sum1(uint64_t i, uint64_t acc)
{
        if (i == 0) {
                return acc;
        } else {
                return sum1(i - 1, i + acc);
        }
}

uint64_t sum(uint64_t n)
{
        return sum1(n, 0);
}

int main (int argc, char *argv[])
{
        printf("%lu\n", sum(atol(argv[1])));
}
$ gcc -O3 10.c
$ ./a.out 100000000
5000000050000000
$ gcc -O0 10.c
$ ./a.out 100000000
Segmentation fault

dave

И я совершенно не представляю, как их реализовать на Си или Си++. Тут столько ограничений платформы (которая, якобы чуть ли не «портабельный ассемблер»).

«портабельный ассемблер» это деление на ноль.

dave

Можно запросто проверить gcc, скормив ей функцию факториала.

можно. Просто посмотрев дизассемблером код. Просто лениво. И смысла нет, ибо в С и С++ так писать не принято. Ибо это не LISP.

Proper Tail Recursion In C, Mark Probst, 2001-02

в общем умеет но весьма ограниченно и с большим числом оговорок, но можно писать «правильный код»

да. Вот как у меня эта функция скомпиллилась:

080483c0 <sum1>:
 80483c0:	55                   	push   %ebp
 80483c1:	89 e5                	mov    %esp,%ebp
 80483c3:	56                   	push   %esi
 80483c4:	53                   	push   %ebx
 80483c5:	8b 55 08             	mov    0x8(%ebp),%edx
 80483c8:	8b 4d 0c             	mov    0xc(%ebp),%ecx
 80483cb:	8b 5d 10             	mov    0x10(%ebp),%ebx
 80483ce:	8b 75 14             	mov    0x14(%ebp),%esi
 80483d1:	89 c8                	mov    %ecx,%eax
 80483d3:	09 d0                	or     %edx,%eax
 80483d5:	74 19                	je     80483f0 <sum1+0x30>
 80483d7:	89 f6                	mov    %esi,%esi
 80483d9:	8d bc 27 00 00 00 00 	lea    0x0(%edi,%eiz,1),%edi
 80483e0:	01 d3                	add    %edx,%ebx
 80483e2:	11 ce                	adc    %ecx,%esi
 80483e4:	83 c2 ff             	add    $0xffffffff,%edx
 80483e7:	83 d1 ff             	adc    $0xffffffff,%ecx
 80483ea:	89 c8                	mov    %ecx,%eax
 80483ec:	09 d0                	or     %edx,%eax
 80483ee:	75 f0                	jne    80483e0 <sum1+0x20>
 80483f0:	89 d8                	mov    %ebx,%eax
 80483f2:	89 f2                	mov    %esi,%edx
 80483f4:	5b                   	pop    %ebx
 80483f5:	5e                   	pop    %esi
 80483f6:	5d                   	pop    %ebp
 80483f7:	c3                   	ret    

$ gcc --version
gcc (GCC) 4.5.3
options: -O3

...на x86 этот быдлокод «всегда» работает. ...

У меня не работает (SUSE Linux Enterprise Server 11 (x86_64)), 3! = 0, если строчку return a; закомментировать.

anonymous

У меня не работает (SUSE Linux Enterprise Server 11 (x86_64)), 3! = 0, если строчку return a; закомментировать.

без оптимизации? с -O0? покажите

$ objdump -d ret | sed '/<fact_rec2>:/,/^$/!d'
080483d4 <fact_rec2>:
 80483d4:	55                   	push   %ebp
 80483d5:	89 e5                	mov    %esp,%ebp
 80483d7:	83 ec 18             	sub    $0x18,%esp
 80483da:	83 7d 08 00          	cmpl   $0x0,0x8(%ebp)
 80483de:	7f 07                	jg     80483e7 <fact_rec2+0x13>
 80483e0:	b8 00 00 00 00       	mov    $0x0,%eax
 80483e5:	eb 27                	jmp    804840e <fact_rec2+0x3a>
 80483e7:	83 7d 08 01          	cmpl   $0x1,0x8(%ebp)
 80483eb:	75 07                	jne    80483f4 <fact_rec2+0x20>
 80483ed:	b8 01 00 00 00       	mov    $0x1,%eax
 80483f2:	eb 1a                	jmp    804840e <fact_rec2+0x3a>
 80483f4:	8b 45 08             	mov    0x8(%ebp),%eax
 80483f7:	48                   	dec    %eax
 80483f8:	83 ec 0c             	sub    $0xc,%esp
 80483fb:	50                   	push   %eax
 80483fc:	e8 d3 ff ff ff       	call   80483d4 <fact_rec2>
 8048401:	83 c4 10             	add    $0x10,%esp
 8048404:	0f af 45 08          	imul   0x8(%ebp),%eax
 8048408:	89 45 f4             	mov    %eax,-0xc(%ebp)
 804840b:	8b 45 f4             	mov    -0xc(%ebp),%eax
 804840e:	c9                   	leave  
 804840f:	c3                   	ret    

А чем ключ -S плох? objdump обязателен?

io

А чем ключ -S плох? objdump обязателен?

просто так у меня получается программа, которую я вовсе не обязательно буду дизассемблировать. Ещё и выполнить могу. Впрочем - дело вкуса конечно.

4.2

http://ridiculousfish.com/blog/posts/will-it-optimize.html

Тебе повезло. Ответ в регистре ax

У вас — баг, в компиляторе — фича.

Есть еще оптимизация, когда хвостовой вызов внутри одной функции заменяется циклом. Это - лишь частный случай оптимизации хвостового вызова. Такое умеют даже Scala c clojure, тогда как в самой JVM нет вовсе поддержки хвостовой рекурсии. Многие почему-то путают и считают, что это и есть вся оптимизация хвостового вызова...

Многие всё время говорят и думают только о «хвостовой _рекурсии_», подразумевая её только в пределах одной функции, которая и разворачивается в цикл, и к «хвостовым вызовам» никак не относится. А «хвостовой вызов» - это действительно тормоз, и использовать/эмулировать его везде не надо.

Соответственно, в JVM нет поддержки _хвостовых вызовов_, что не мешает некоторым компиляторам на JVM поддерживать «хвостовую рекурсию в пределах одного метода».

Программисты любят изобретать свою терминологию :) Относится, напрямую.

С какой это радости хвостовой вызов «тормоз»? Две инструкции - срезать SP и безусловный переход по адресу. Call обычно дороже.

С какой это радости хвостовой вызов «тормоз»? Две инструкции - срезать SP и безусловный переход по адресу. Call обычно дороже.

Эмм... Ты сейчас привёл универсальное решение для всех камней, ОС и «систем вызовов»?

Программисты любят изобретать свою терминологию :)

Это не ко мне :)

Относится, напрямую.

Ну?

А вот в perl функция возвращает последнее вычисленное значение. В perl эту строчку действительно можно не писать!

без оптимизации? с -O0? покажите ...

$ cat tryf.c
#include "stdio.h"
  int fact_rec2(int n)
  {
    int a;
    if(n<1) return 0;
    if(n==1) return 1;
    a=n*fact_rec2(n-1);
    //    return a;
  }

int main(int argc, char* argv[])
{
  int x;//=0;
  scanf("%d",&x);
  printf("%d\n",fact_rec2(x));
  return 0;
}

$gcc -O0 -o tryf tryf.c
$./tryf
3
0
$ objdump -d tryf |sed '/<fact_rec2>:/,/^$/!d'
00000000004005ac <fact_rec2>:
4005ac:       55                      push   %rbp
4005ad:       48 89 e5                mov    %rsp,%rbp
  4005b0:       48 83 ec 20             sub    $0x20,%rsp
  4005b4:       89 7d ec                mov    %edi,-0x14(%rbp)
  4005b7:       83 7d ec 00             cmpl   $0x0,-0x14(%rbp)
  4005bb:       7f 09                   jg     4005c6 <fact_rec2+0x1a>
  4005bd:       c7 45 e8 00 00 00 00    movl   $0x0,-0x18(%rbp)
  4005c4:       eb 23                   jmp    4005e9 <fact_rec2+0x3d>
  4005c6:       83 7d ec 01             cmpl   $0x1,-0x14(%rbp)
  4005ca:       75 09                   jne    4005d5 <fact_rec2+0x29>
  4005cc:       c7 45 e8 01 00 00 00    movl   $0x1,-0x18(%rbp)
  4005d3:       eb 14                   jmp    4005e9 <fact_rec2+0x3d>
  4005d5:       8b 45 ec                mov    -0x14(%rbp),%eax
  4005d8:       8d 78 ff                lea    -0x1(%rax),%edi
  4005db:       e8 cc ff ff ff          callq  4005ac <fact_rec2>
  4005e0:       0f af 45 ec             imul   -0x14(%rbp),%eax
  4005e4:       89 45 fc                mov    %eax,-0x4(%rbp)
  4005e7:       eb 06                   jmp    4005ef <fact_rec2+0x43>
  4005e9:       8b 45 e8                mov    -0x18(%rbp),%eax
  4005ec:       89 45 e4                mov    %eax,-0x1c(%rbp)
  4005ef:       8b 45 e4                mov    -0x1c(%rbp),%eax
  4005f2:       c9                      leaveq
  4005f3:       c3                      retq

э... вам не повезло - 64и бита однако. А вот int a оно всё равно 32х битное. наверное в этом проблема.

...А вот int a оно всё равно 32х битное.

Ну да, конечно...

У меня gcc выдает (и должен выдавать!) ошибку о том, что функция, возвращающая int, не возвращает ничего. Значит, любой пример успешной работы программы - всего лишь случайность