C ++ đệ quy

Trong hướng dẫn này, chúng ta sẽ tìm hiểu về hàm đệ quy trong C ++ và cách hoạt động của nó với sự trợ giúp của các ví dụ.

Một hàm gọi chính nó được gọi là một hàm đệ quy. Và, kỹ thuật này được gọi là đệ quy.

Làm việc của đệ quy trong C++

void recurse()
{
    ... .. ...
    recurse();
    ... .. ...
}

int main()
{
    ... .. ...
    recurse();
    ... .. ...
}

Hình dưới đây cho thấy cách hoạt động của đệ quy bằng cách gọi đi gọi lại chính nó.Cách đệ quy hoạt động trong lập trình C ++

Đệ quy tiếp tục cho đến khi một số điều kiện được đáp ứng.

Để ngăn chặn đệ quy vô hạn, câu lệnh if … else (hoặc cách tiếp cận tương tự) có thể được sử dụng khi một nhánh thực hiện lệnh gọi đệ quy và nhánh kia thì không.

Ví dụ 1: Giai thừa của một số sử dụng đệ quy

// Factorial of n = 1*2*3*...*n

#include <iostream>
using namespace std;

int factorial(int);

int main() {
    int n, result;

    cout << "Enter a non-negative number: ";
    cin >> n;

    result = factorial(n);
    cout << "Factorial of " << n << " = " << result;
    return 0;
}

int factorial(int n) {
    if (n > 1) {
        return n * factorial(n - 1);
    } else {
        return 1;
    }
}

Đầu ra

Enter a non-negative number: 4
Factorial of 4 = 24

Hoạt động của Chương trình Giai thừa

Cách hoạt động của chương trình đệ quy C ++ này

Như chúng ta có thể thấy, factorial()hàm đang gọi chính nó. Tuy nhiên, trong mỗi cuộc gọi, chúng tôi đã giảm giá trị của n bằng 1. Khi n nhỏ hơn 1, factorial()hàm cuối cùng trả về đầu ra.

Ưu điểm và nhược điểm của đệ quy

Dưới đây là những ưu và nhược điểm của việc sử dụng đệ quy trong C ++.

Ưu điểm của đệ quy C ++

It makes our code shorter and cleaner.
Recursion is required in problems concerning data structures and advanced algorithms, such as Graph and Tree Traversal.