Hỏi trình tự chạy của hàm đệ quy in ra dãy đảo ngược

Phan_Minh_Tien1 · June 14, 2019, 2:12am

#include <stdio.h>
int main() {
    char c;
    if ( ( c = getchar() ) != '\n' ) main();
    putchar( c );
    return 0;
}

Các bác cho em hỏi là trình tự nó chạy như nào nếu mình nhập abc vào với ạ hic hic

Sherly1001 · June 12, 2019, 1:36pm

Bạn ơi, bạn format lại source code hộ mình nha.

Quay trở lại vấn đề của bạn. Nếu bạn nhập abc Enter thì:

Trong stream (tức stdin) có chuỗi abc\n.
getchar() sẽ lấy từng chữ cái một.
Đầu tiên c = getchar() = 'a' != '\n' lại gọi hàm main() tạm đặt tên là main tập 1.
Và trong main tập 1:
- c = getchar() = 'b' != '\n' thế là gọi tiếp một thằng main() nữa, đây là main tập 2.
- Trong main tập 2:
  - c = getchar() = 'c' != '\n' lại gọi main tập 3.
  - Trong main tập 3:
    - c = getchar() = '\n' != '\n' đến đây if bị sai, không gọi main tập 4.
    - putchar(c) lúc này c = '\n' xuống dòng.
    - Về main tập 2.
  - putchar(c) lúc này c = 'c' in ra c.
  - Về main tập 1.
- putchar(c) lúc này c = 'b' in ra b.
- Về main gốc hay có thể gọi là main tập chai-lơ.
putchar(c) lúc này c = 'a' in ra a.
Gặp anh return 0 out.

Mong bạn có thể hiểu.

Phan_Minh_Tien1 · June 12, 2019, 2:45pm

kiểu này gọi là đệ quy đầu phải không ạ ? Anh có thể giải thích cho e 1 ví dụ về đệ quy đuôi được ko ạ hic hic, 2 cái này em cảm thấy khá khó phân biệt

hungaya · June 12, 2019, 3:38pm

Với giải thuật đệ quy thì điều cấm kị là hiểu giải thuật theo cách debug vào callstack, chạy main() rồi truy tiếp main(), trong main() con truy vết tiếp main() cháu, main() cháu gọi main() chắt,…

Cách để đọc hiểu đó là sử dụng phương pháp quy nạp (induction). Mình sẽ chỉ để bạn có cách đọc hiểu ghi gặp các dạng đệ quy sau. (dễ mới chỉ, khó mình sẽ không chỉ, vì không biết cách )

Gọi P(n) là vị từ: Khi chạy hàm main() với input có chiều dài n là “a₁ a₂ … a_n” thì output ngược lại với input, tức là “a_n a_n-1 … a₂ a₁”

Base case: P(0)
Input là chuỗi rỗng, hay người nhập chỉ nhấn enter => kí tự ‘\n’ => if không thực hiện, putchar() chỉ thực hiện xuống dòng, không có kí tự nào hiển thị.
Vậy, P(0) đúng.

Inductive Step: P(n) => P(n+1)
Giả sử P(n) đúng với n ≥ 0. Việc còn lại là chứng minh P(n+1) đúng.
Input cho P(n+1) có chiều dài n+1, có dạng “a₁ a₂ … a_n a_n+1”.
Chạy hàm main():

Gọi lệnh if kiểm tra a₁ != ‘\n’, trả về true, nên gọi tiếp main() con
Trong main() con thực hiện với chuỗi “a₂ … a_n a_n+1” có chiều dài n. Áp dụng giả thuyết P(n), main() con cho output là “a_n+1 a_n … a₂”
Sau lệnh if, chạy lệnh putchar(a₁) in ra a₁, output cuối cùng “a_n+1 a_n … a₂ a₁”

Vậy P(n) => P(n+1) là mệnh đề đúng.

Từ base case và inductive step, P(n) đúng với mọi n, giải thuật được chứng minh.

Tail-call recursion:

#include <stdio.h>

void push_front(char str[], int n, char c) {
    for (int i = n + 1; i > 0; i--)
        str[i] = str[i-1];
    str[0] = c;
}

void reverse(char str[], int n) {
    char c;
    if ((c = getchar()) != '\n') {
        push_front(str, n, c);
        reverse(str, n + 1);
    }
}

int main() {
    char str[50] = { '\0' };
    reverse(str, 0);
    printf("%s\n", str);
}

Sherly1001 · June 12, 2019, 3:06pm

Đúng rồi bạn, như code bạn đưa thì là đệ quy đầu. Vẫn ví dụ đó nhưng là đệ quy ngược.

#include <stdio.h>

int main() {
	char c = getchar();
	putchar( c );
	if (c != '\n')
		main();
	return 0;
}

input: abc
output: abc

Phan_Minh_Tien1 · June 12, 2019, 3:17pm

anh có thể giúp cho em hiểu trình tự được ko ạ ? Tại cái nãy a viết làm e hiểu kha khá :v . Em chân thành cảm ơn a

Sherly1001 · June 12, 2019, 3:38pm

Cũng đơn giản mà, bạn có thể đọc từng dòng code rồi hình dung mình cũng như một cái máy tính, chạy lần lượt từng dòng code một cứ theo thứ tự mà chạy. Còn không thì debug cũng được.

Trình tự của bạn:

Chạy main chai-lơ. Nhập abc\n.
c = getchar() = 'a'
putchar(c) in ra a.
if đúng vào main tập 1:
- c = getchar() = 'b'
- putchar(c) in ra b.
- if lại đúng gọi main tập 2:
  - c = getchar() = 'c'
  - putchar(c) in ra c.
  - if vẫn đúng gọi main tập 3:
    - c = getchar() = '\n'
    - putchar(c) xuống dòng.
    - Lúc này thì if bị sai
  - về main tập 2.
  - Không có gì.
- về main tập 1.
- Vẫn không có gì.
Về main chai-lơ.
return 0 hết phim.