Inkrementacja zmiennej przez rekurencję

Question

Rozpatrzmy poniższy, prosty program w języku C/C++:

#include <stdio.h>
int increment(int n)
{
   return (n<100000) ? increment(n+1) : n;
}
int main()
{
   int a=increment(1);
   printf("%d", a);
}

Program powinien dokonać wielokrotnego wywołania funkcji increment przez rekurencję, która wykonuje się tak długo, aż wartość zmiennej n nie będzie równa 100000 (i taka liczba ma być wypisana). Niestety, tuż po uruchomieniu programu zwracany jest jedynie błąd  -1073741571 (0xC00000FD). Tego problemu nie ma, gdy w warunku zamiast wartości 100000 jest liczba mniejsza od 65144, np. return (n<50000) ? increment(n+1) : n; (program wypisuje poprawnie 50000). Gdy zmienimy argument funkcji increment na 2, najwyższą porównywaną liczbą będzie 65144, gdy będzie to 3 - 65145 itd.

W czym tkwi problem?

Answer 1

Odpowiedz to stos wywołań ;) Gdy wykonujesz rekurencje to komputer musi sobie zapamiętać że

- wartość pierwszego wywołania funkcji to
- wartość drugiego wywołania funkcji której
- wartość to trzecie wywołanie funkcji której
- wartość to 4.
- więc trzecie wywołanie zwraca 4 
- a skoro trzecie to 4 to drugie to też 4
- a skoro drugie zwraca 4 to 
- pierwsze też może zwrócić 4

Chodzi o to że podczas rekurencji musisz przechowywać w pamięci całą kolejność wywołań funkcji aby potem zacząć przekazywać do niej wartość od tyłu. Niestety przechowywanie kolejności wywołań funkcji ma swoje ograniczenia i przekroczenie ograniczenia jest na tyle popularne że przyczyniło się do nazwania jednego forum internetowego: stack overflow ;)

Answer 2

Popatrz na linijkę 15.

https://godbolt.org/z/aP7jW7r5T

Jak widzisz, jest tam obecna instrukcja asemblerowa call. Oznacza to że przy każdym wywołaniu, odkładane są informacje na stosie. Przy tak dużej ilości wywołań, następuje przepełnienie stosu.

A teraz dodaj przełącznik optymalizacji np ze względu na prędkość.

https://godbolt.org/z/PYcnscnzx

Jak widać kompilator zamienił call, na jmp.

A dzieje się tak dlatego, że w standardzie języka C ani C++ nigdzie nie ma zapisu że kompilator ma obsługiwać rekurencję. Tylko od życzliwości dostawcy kompilatora zależy, czy dany kompilator będzie to obsługiwał.

BTW: g++ obsługuje rekurencję poprawnie już bez przełączników optymalizacji.

Comments

Dziwnie piszesz. Nie studiowałem dogłębnie standardów, ale zawsze mnie uczono, że C obsługuje rekurencje.

To, że kompilator w ramach optymalizacji sobie coś tam pozmienia to inna sprawa.

---

Ok, wykonałem nieprecyzyjny skrót myślowy. Sugerowałem się pytaniem w trybie "a dlaczego to nie działa". No to może nieco obszerniej.

C tak jak i C++, nigdzie nie deklaruje w standardzie że rekurencja ma być obsługiwana "z optymalizacją" i na jakim poziomie samej optymalizacji kompilatora. Taka rekurencja nazywana jest tail call lub tail recursion ( https://en.wikipedia.org/wiki/Tail_call ). Haskell to ma, Scheme i pochodne Lisp'a C i C++ ... (jak większość języków imperatywnych) ... może tak a może nie... :/

Natomiast standard C++, opisuje np. obsługę main() :) Nie powinno się jej wołać rekurencyjnie (6.9.3.1 2.2.3) http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2020/n4849.pdf

Dlatego rekurencja dla C i C++ dla kodu produkcyjnego jest zabroniona, bo nie każdy dostawca i nie na każdym poziomie optymalizacji swojego kompilatora, może ją implementować.

https://helloacm.com/understanding-tail-recursion-visual-studio-c-assembly-view/

... tu trochę o trampolinie która zapewni obsługę optymalizacji zawsze...

https://www.artificialworlds.net/blog/2012/04/30/tail-call-optimisation-in-cpp/

Uff.. Mam nadzieję że teraz jasne :)