Ndaadn

Hiếm khi gặp được bác nào tìm hiểu sâu đến mức compile xong xem cả Assembly code Mình vốn cũng không hiểu sâu về việc Optimize của compiler lắm nhưng đọc được câu hỏi này thì có hứng thú tìm hiểu

• Để trả lời trực tiếp câu hỏi, thì bác có thể xem document của GCC ở đây: https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html
  

Đầu tiên là về flag Os:

-Os Optimize for size. -Os enables all -O2 optimizations except those that often increase code size:
-falign-functions -falign-jumps
-falign-labels -falign-loops
-fprefetch-loop-arrays -freorder-blocks-algorithm=stc
It also enables -finline-functions, causes the compiler to tune for code size rather than execution speed, and performs further optimizations designed to reduce code size.

Có nghĩa là flag -Os sẽ bằng flag -O2 cộng thêm các flag tối ưu khác. Ctrl + F lên flag -O2 nội dung như sau:

-O2
Optimize even more. GCC performs nearly all supported optimizations that do not involve a space-speed tradeoff. As compared to -O, this option increases both compilation time and the performance of the generated code.
-O2 turns on all optimization flags specified by -O. It also turns on the following optimization flags:
.....
-foptimize-sibling-calls
.....

Vậy là flag -O2 bao gồm flag -O và thêm rất nhiều flag optimize khác của compiler. Và để ý flag -foptimize-sibling-calls trên.

-foptimize-sibling-calls
Optimize sibling and tail recursive calls.
Enabled at levels -O2, -O3, -Os.

Tức là nó sẽ tối ưu sibling (sibling là lời gọi đệ quy chéo, tức là 2 hàm gọi đệ quy lẫn nhau) và các lời gọi đệ quy đuôi.
Có nhiều cách phân loại kiểu đệ quy, nhưng thường sẽ phân loại là đệ quy đuôi (tail-recursion) và đệ quy không phải là đệ quy đuôi (non tail-recursion) hay gọi đơn giản là đệ quy thường.

• Đệ quy đuôi là hàm đệ quy mà lệnh gọi đệ quy là lệnh cuối cùng được gọi của hàm.

Đệ quy đuôi có dạng như thế này (mình viết psuedo code thôi, hy vọng dễ hiểu):

P(U):
begin
    if C then 
             D
             P(a(U))
    else
            T
    endif
end

• Với U là danh sách tham số.
• C là biểu thức điều kiện nào đó.
• D là các câu lệnh xử lý cơ bản nào đó.
• a(U) là một sự chuyển đổi tham số nào đó, ví dụ như ở hàm Fibonacci: Fibonacci(index - 1, second, first + second) thì a(U) là index-1, second, first+second chẳng hạn.
• T là xử lý dừng, tức là câu lệnh return.

Đệ quy đuôi có thể tối ưu bằng cách khử đệ quy thành vòng lặp. Dạng hàm sau khi khử đệ quy đuôi của hàm trên như sau:

P2(U):
begin
     while C do
            D
            U = a(U)
     endwhile
     T
end

Ví dụ hàm Fibonacci trong câu hỏi là một dạng đệ quy đuôi:

long int Fibonacci(long int index, long int first, long int second) {
    if (index == 0) return first;
    return Fibonacci(index - 1, second, first + second);
}

Khi khử đệ quy nó sẽ có dạng giống như tính bằng vòng lặp:

long int Fibonacci(long int index, long int first, long int second) {
    while(index != 0) {
        index = index - 1;
        first = second;
        second = first + second
    }    
    return second;
}

Đệ quy thường có dạng như thế này:

Q(U):
begin
    if C then
        D1(U)
        Q(a(U))
        D2(U)
    else
        T
    endif
end

Khử đệ quy cần phải dùng thêm Stack S:

Q2(U):
begin
    create(S)
    while C do
        D1(U)
        push(S, U)
        U = a(U)
    endwhile
    T
    while not isempty(S) do
        U = top(S)
        D2(U)
        pop(S)
    endwhile
end

======================================================================
Phần trên là về lý thuyết. Còn đây là suy nghĩ của mình, đối với đệ quy đuôi, việc khử đệ quy thành vòng lặp giúp tối ưu chương trình bằng cách bỏ bớt việc tạo stack. Còn với kiểu đệ quy thường, việc khử đệ quy thành vòng lặp vẫn cần phải tạo Stack để lưu trữ, vậy nên sẽ không có nhiều ý nghĩa tối ưu. Nên khi thêm flag -Os vào lệnh compile, nó sẽ tối ưu cho đệ quy đuôi bằng cách khử đệ quy thành vòng lặp. Các ví dụ trong câu hỏi có dạng đệ quy đuôi đều được tối ưu bằng cách khử đệ quy. Riêng trường hợp

long int sumArray(long int* seq, long int size) {
    if (size == 0) return 0;
    return *seq + sumArray(seq + 1, size - 1);
}

Theo định nghĩa trường hợp này không phải là đệ quy đuôi, vì thực chất lời gọi đệ quy không phải là bước thực hiện cuối cùng của hàm. Thực tế hàm này có dạng như thế này:

long int sumArray(long int* seq, long int size) {
    if (size == 0) return 0;
    long int k = sumArray(seq + 1, size - 1);
    return *seq + k;
}

Vậy nên câu trả lời cho câu hỏi sẽ là, với flag -O2 trở lên, compiler sẽ thực hiện tối ưu khử đệ quy thành vòng lặp cho các lời gọi đệ quy đuôi và đệ quy chéo (bài viết mình không nói về đệ quy chéo nhưng bác có thể tự tìm kiếm dễ dàng bằng google).

Nên nó không phải là đệ quy đuôi! Có thể xem về ví dụ dễ nhầm lẫn này ở link sau: https://stackoverflow.com/questions/310974/what-is-tail-call-optimization

Và câu trả lời về việc GCC hay G++ có tối ưu đệ quy đuôi hay không ở link sau: https://stackoverflow.com/questions/34125/which-if-any-c-compilers-do-tail-recursion-optimization