Đệ quy thực hiện các lệnh như thế nào?

#1

Trong video về phần đệ quy của @NguyenVietNamSon,mình thấy khi giải bài toán:
Tính tổng:S=1+2+3+4+5+6+7+…+N.thì anh Sơn code như sau:

int tinhtong(int N,int sum=0,int i=0){
    if(i>N)
        return sum;
    return tinhtong(N,sum+i,i+1);
}
int main(){
    int N=12;
    printf("Tong can tim bang: %d.\n",tinhtong(N));
    return 0;
}

Nhưng mình code lại thế này vẫn nhận được kết quả như nhau.Ở đây mình bỏ lệnh return khi gọi lại hàm tinhtong.

int tinhtong(int N,int sum=0,int i=0){
    if(i>N)
        return sum;
    tinhtong(N,sum+i,i+1);
}
int main(){
    int N=12;
    printf("Tong can tim bang: %d.\n",tinhtong(N));
    return 0;
}

Cụ thể:
INPUT:

N=12;

OUTPUT:

sum=78;

Nhờ mọi người giải thích giúp mình về tác dụng của lệnh return trong trường hợp này.

#2

return là để trả lại giá trị của 1 hàm nào đó.
Trong TH của bạn hay bài mẫu của bạn Sơn đều gọi đến hàm tinhtong(N, sum+i, i+1) nên nó đều thực hiện hàm đó. Nhưng khác nhau ở đâu?
Khác ở chỗ nếu không có return thì nó sẽ thực hiện tiếp các lệnh sau đó. Còn nếu có return thì các lệnh sau sẽ không được thực hiện.

Bạn thử chạy code này xem kết quả nhé.

#include <stdio.h>
int tinhtong(int N,int sum=0,int i=0){
    if(i>N)
        return sum;
    tinhtong(N,sum+i,i+1);
    printf("%d\t",i);
}

int main(){
    int N=12;
    printf("Tong can tim bang: %d.\n",tinhtong(N));
    return 0;
}
1 Like
#3

Đệ quy là một kĩ thuật tương tự vòng lặp nhưng có lưu cấu hình ở từng thời điểm tự gọi hàm và có quay lui ở thời điểm return.

1 Like
#4

Cho mình hỏi tại sao đến khúc

tinhtong(…); mà nó lại có thể thực hiện được dòng tiếp theo của nó là dòng printf . mặc dù nó phải chạy lại hàm đó ?? mà mình cũng chưa hiểu lắm về đoạn code trên nếu ta không có ’ return ’ tại hàm ’ kết quả của nó lại là ‘2’ ?

Mọi người có thể giúp mình giải thích nó được chứ .
Cảm ơn mọi người

#6

Bổ sung thêm là hàm đệ quy trên khá phức tạp vì phải tính kq bài toán qua biến phụ là sum và i và nó khá giống 1 vòng for :c
Có 1 cách đệ quy tương tự nhưg đơn giản hơn ^^ Bạn xem tham khảo và tập debug nhé ^^

int A(int n) {
 if(n==1) return n;
 else return n+A(n-1);
}
int main() { printf("%d",A(5)); return 0; }
3 Likes
#7

ý mình là tại sao sau cái hàm

nó lại chạy được cái printf ý @@

#8

Sr bạn ~~
đọc ko kỹ rồi chém lung tung ~~
function trong C có thể coi là 1 biến đặc biệt ~~
Như ở Pascal sẽ thể hiện rõ điều này. Có thể gán function = 1 giá trị bất kì nào ở chương trình function ở Pascal.
C thì ko có gán trực tiếp đc, nó chỉ được gán gián tiếp qua hàm return.
Và ở post mình xóa đi có nói sai 1 chút rằng nếu ko return nó sẽ ko thực hiện đc. Đúng là sẽ in ra kq sai, nếu hàm đó ko lấy được giá trị nào từ hàm khác. ^^

3 Likes
#10

Không có gì đâu bạn bạn onl giờ này trả lời cho mình là hay lắm rồi :smiley:

mình cứ tưởng khi nó gọi hàm

là nó sẽ bỏ qua luôn printf chứ nhỉ @@ ai zè

#11

theo mình nghĩ là nó return sum xong lại quay ngược lại làm các lệnh tiếp theo. kiểu thoát khỏi vòng lặp ấy.

#12

Đây là đệ quy đuôi. Tốc độ của nó nhanh hơn nhiều với đệ quy tuyến tính . Trường hợp này hàm trả về kiểu int nhưng bạn đệ quy ko thực hiện return thì nó sẽ ko gọi lại chính nó. Kết quả là sai chư ko đúng. Đã test trên visual kết quả ra 2. Bạn kiểm tra xem có nhầm lẫn với void tinhtong(int N, int sum = 0, int i = 0) ko? vì hàm void ta gọi lại hàm thì ko có return như trên . !

#13

Mình vẫn hay lấy ví dụ này để giải thích đệ quy cho người khác:

#include <iostream>
using namespace std;

void recursion(int i)   {
    if(i == 10)
        return;

    cout << i << " ";

    recursion(i+1);

    cout << i << " ";
}

int main()  {
    recursion(1);
    return 0;
}
3 Likes
#14

2 posts were split to a new topic: Hàm đệ quy kiểu void thực hiện đảo ngược số không dừng được

#15

anh ơi anh có thể giải thích giùm em được không? em có chay debug thử code này khi tính tổng xong tới dòng printf("%d", i); thì i lại giảm theo công thức i-- xong thằng tinhtong(N,sum+i,i++); cũng giảm dần theo công thức sum - i luôn .

#16

i--, tinhtong(N,sum+i,i++);, sum - i ở đâu vậy, có thấy trong code trên đâu?

P/s: đọc post #11 của @nguyenchiemminhvu ở trên nhé.

3 Likes
#17

không thấy trong code nhưng lúc debug giá trị nó như vậy á ông. lúc chay xong tới dòng tinhtong(N,sum+1,++I); dến dòng printf("%d", i); thì bài toán nó bắt đầu tính cái tui nói á.

#18

Cắm “Watch” đó :smiley:

Mỗi lần gọi callee tạo ra 1 frame gồm có N, sum, i cho lần gọi đó, để khi trả điều khiển về caller thì caller lôi ra sử dụng tiếp đến khi hàm chạy xong.

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?