Không hiểu rõ việc sử dụng đệ quy cho danh sách liên kết

Kate_20401 · August 3, 2020, 3:02am

Em chào mọi người!
Em mới được bạn gửi cho một cái đề, trong số những bài đó yêu cầu là phải sử dụng đệ quy cho danh sách liên kết. Em không hiểu rõ lắm về việc sử dụng hai cái này với nhau( tại em chỉ mới sử dụng đệ quy cho mảng) .
Mọi người có thể chỉ em cách làm/ hay một ví dụ/một trang web nào về việc sử dụng đệ quy cho danh sách liên kết được không?( Tại em không hình dung được việc sử dụng đệ quy cho DSLK) .
Em cảm ơn mọi người nhiều!

rogp10 · August 3, 2020, 5:08am

Khi gọi hàm thì hàm gọi (caller) vẫn giữ trạng thái lúc đó chờ hàm được gọi trả về

Vậy đệ quy 1 lời gọi có thể dùng để duyệt chiều ngược của DSLK đơn.

Kate_20401 · August 3, 2020, 7:26am

Minh vẫn chưa hiểu lắm, bạn có thể giải thích rõ hơn cho mình được không T_T ( Nếu có ví dụ thì càng tốt) Mong bạn chỉ mình thêm

phamvandung · August 3, 2020, 9:38am

Bài tập đệ quy với danh sách chủ yếu để rèn luyện tư duy cho bạn nên cứ làm thôi :)) Sau này học đến những thứ như cây thì việc sử dụng đệ quy là bắt buộc, đòi hỏi bạn phải quen với nó và áp dụng được.
Dưới đây là ví dụ 3 hàm sử dụng đệ quy. Việc của bạn là làm những hàm còn lại chỉ sử dụng đệ quy. Nó sẽ giúp tư duy của bạn đỉnh hơn trước rất nhiều, chắc chắn luôn.

hàm insert_last: thêm 1 phần tử vào cuối danh sách. Base case là nếu phần tử nhập vào là phần tử cuối cùng thì thêm vào ngay sau nó. Nếu phần tử nhập vào chưa phải phần tử cuối thì gọi lại hàm cho phần tử next của nó.
hàm print: in các phần tử từ đầu đến cuối: chỉ in ra giá trị phần tử nhập vào, sau đó gọi tiếp hàm print này đối với phần tử next, nếu next == NULL thì thôi.
hàm print_invert: như hàm print nhưng in ngược lại từ cuối lên đầu. Gọi in phần tử tiếp theo trước sau đó mới in phần tử hiện tại. Nếu không dùng đệ quy thì bạn phải dùng 1 mảng để lưu từng giá trị. Bạn thử làm xem :V

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
  int val;
  struct node* next;
} Node;


void insert_last(Node* root, int val) {
  if (root->next == NULL) {
    Node* new_node = malloc(sizeof(Node));
    new_node->next = NULL;
    new_node->val = val;
    
    root->next = new_node;
  } else {
    insert_last(root->next, val);
  }
}

void print(Node* root) {
  printf("%d, ", root->val);
  if (root->next != NULL) {
    print(root->next);
  } 
}

void print_invert(Node* root) {
  if (root->next != NULL) {
    print_invert(root->next);
  }
  printf("%d, ", root->val);
}

int main(void) {
  Node root = {1, NULL};

  for (int i = 2; i < 10; i++) {
    insert_last(&root, i);
  }
  print_invert(&root);
  
  // lười free 
}

Kate_20401 · August 3, 2020, 11:25am

Cảm ơn bạn nhiều !!! Mình sẽ code thử!