Cần giải thích 3 dòng đệ quy trong code Tháp Hà Nội

[Tran_Vinh_Quang (Trần Vinh Quang)]

Bác nào rảnh có thể giải thích rõ cho e 3 dòng đệ quy thapHaNoi đc ko ạ
E biết cách làm nhưng lại không hiểu code lắm (e mới học đệ quy, các bác ném nhẹ tay).

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

void thapHaNoi(int n, char a, char b, int c){
    if(n == 1) {
        printf("\n\t%c-----%c", a, c);
        return;
    }
    else {
        thapHaNoi(n-1, a, c, b);
        thapHaNoi(1, a, b, c);
        thapHaNoi(n-1, b, a, c);
    }
}

int main(int *argc, char*argv[]){
    int n;
    char a = 'A', b = 'B', c = 'C';
    scanf("%d", &n);
    thapHaNoi(n, a, b, c);

    return 0;
}

[hoangthan (Breaker)]

ai hồi mới học cũng thế thôi, bài này bạn cứ hiểu tư tưởng tổng quát là được.

• Nếu có 1 đĩa thì chuyển từ A -> C luôn không nói nhiều.

• Lớn hơn 1 đĩa :

            1. Chuyển n-1 đĩa từ A- >B(chuyển như thế nào thôi chưa xét tới vội) 
            2. Chuyển đĩa còn lại từ A -> C 
            3. Chuyển n-1 đĩa vừa mang tạm sang B về C. (chuyển như thế nào thôi chưa xét tới vội) 
  

• Nhìn 1 với 3 là bạn thấy ngay, về bản chất nó không khác gì so với bài toán gốc, có chi thì chỉ là số lượng ít hơn và tên cột nguồn, đích khác nhau. Cái chính là bạn phải nắm được “tư tưởng đệ quy” là nắm cái quy luật chính của cả bài toán.

  1. Chuyển n-1 đĩa từ A- >B nó chính là bài toán ban đầu với nguồn là A, đích là B. Khi nó được gọi đệ quy thì nó lại giải quyết vậy làm sao để chuyển n-1 đĩa từ A- >B ? Lại chia nhỏ bài toán ra, lại chuyển n-2 đĩa từ A->C, chuyển đĩa còn lại từ A->B rồi chuyển n-2 đĩa từ C về lại B. Vậy làm sao để chuyển n-2 đĩa từ A->C…

Bài toán được chia nhỏ, nhỏ đến khi nó chạm đến điều kiện mà có thể giải quyết(base case là chỉ còn có 1 đĩa if(n==1)…)

Nắm tư tưởng, đọc code và vẽ lại ra giấy bạn sẽ hiểu nhanh thôi. Good luck