Nhờ giúp đỡ giải thích đoạn code về đệ quy phi tuyến tính

[Hoai_Nam_Truong (Hoài Nam Trương)]

chào m.n , mình có một đoạn code về đệ quy phi tuyến tính , nhưng vẫn không hiểu lắm , về tính chất thì mình hiểu , nhưng lúc debug thì phần tính toán của nó hơi khó hiểu , mong m.n giải thích giúp mình đoạn code này , ths all

#include <iostream>

using namespace std;

int sum(int n)
{
    if(n==0)
        return 1;
    long s = 0;
    for(int i = 1;i<=n;i++)
        s = s+i*i*sum(n-i);
    return s;
}
int main()
{
    int n,m;
    cout << "Nhap N: ";
    cin >> n;
    m = sum(n);
    cout << "ket qua = " << m;
}

[noz1995 (Trần Hoàn)]

Nói chung là nó cứ tính lần lượt từ trong ra ngoài thôi, kiểu như này:

Thắc mắc về đệ quy, mong được giải đáp

sum(5) = 5/6 + 4/5 + 3/4 + 2/3 + 1/2 = 5/6 + sum(4) Và nếu tính chi tiết thì sẽ là 5/6 + sum(4) = 5/6 + 4/5 + sum(3) = 5/6 + 4/5 + 3/4 + sum(2) = 5/6 + 4/5 + 3/4 + 2/3 + sum(1) = 5/6 + 4/5 + 3/4 + 2/3 + 1/2 + sum(0) = 5/6 + 4/5 + 3/4 + 2/3 + 1/2 + 0 vì if(n<=0) return 0;

Hỏi về Đệ quy cùa thuật toán Fibonaci

[image] Hy vọng bạn sẽ hiểu

[Hoai_Nam_Truong (Hoài Nam Trương)]

mình không hiểu lắm
ví dụ lúc mình nhập 3 kết quả là 18
mình debug thử từng lúc tính toán thì lúc đầu như thế này
s(0) = 0 + 1 * 1 * s(2)
s(0) = 0 + 1 * 1 * s(1)
s(0) = 0 + 1 * 1 * s(0)
s(0) = 1
lúc đầu chương trình nó chạy như thế , ở s và i thì nó không tăng lên giá trị gì cả chỉ có 0 và 1 tới lần thứ 2 thì nó mới tăng lên rồi sau đó mình không biết nó tính kiểu gì mà ra 18 luôn

[noname00 (HK boy)]

s và i thì nó không tăng lên giá trị gì cả

Giá trị của i phụ thuộc vào n mà.
Bạn thử in ra i, n trước mỗi bước cộng đệ quy và sum sau mỗi bước cộng đệ quy để xem kĩ hơn.

[Hoai_Nam_Truong (Hoài Nam Trương)]

ví dụ giờ mình nhập 2 , kết quả sẽ là 5 , bạn có thể ghi giúp mình phần tính toán được không ? , tại giờ net sắp đóng cửa , nên mình không debug được.

[noname00 (HK boy)]

n = 2 -> for (i = 1 -> 2) -> tính sum(2 - 1) = sum(1), sum(2 - 2) = sum(0)
n = 1 -> for (i = 1 -> 1) -> tính sum(1 - 1) = sum(0)
n = 0 -> return 1

[Hoai_Nam_Truong (Hoài Nam Trương)]

thế còn lúc trả về kết quả ? , làm sao nó ra 5 thế bạn.

[noname00 (HK boy)]

sum(2) = 1 * 1 * sum(1) + 2 * 2 * sum(0)
sum(1) = 1 * 1 * sum(0)
sum(0) = 1

Tính ngược lại:

sum(1) = 1 * 1 * sum(0) = 1 * 1 * 1 = 1
sum(2) = 1 * 1 * sum(1) + 2 * 2 * sum(0) = 1 * 1 * 1 + 2 * 2 * 1 = 5

[Hoai_Nam_Truong (Hoài Nam Trương)]

okay thank bạn , mình hiểu r