Đệ quy trực tiếp và gián tiếp trong Python là gì?

Đệ quy là một quá trình lặp đi lặp lại một quá trình cho đến khi một điều kiện được đáp ứng. Trong lập trình, quá trình này được lặp lại dưới dạng gọi hàm

Vì vậy, trong ngữ cảnh lập trình đệ quy là một quá trình trong đó một hàm được gọi chính nó cho đến khi một điều kiện được đáp ứng.

Các hàm này được gọi là hàm đệ quy

cần đệ quy

Đệ quy được sử dụng để giải quyết các vấn đề có thể được giải quyết bằng cách gọi lặp lại cùng một chức năng. Nó chia bài toán thành các bài toán con nhỏ hơn và sau đó giải đệ quy từng bài toán con đó

Bất kỳ vấn đề nào có thể được chia thành các vấn đề con nhỏ hơn đều có thể được giải quyết bằng đệ quy

Ví dụ: nếu chúng ta gặp sự cố khi tìm chuỗi fibbonacci, hãy viết nó là

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(fib(n));
    }

    public static int fib(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return fib(n-1) + fib(n-2);
        }
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(fib(n));
    }

    public static int fib(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return fib(n-1) + fib(n-2);
        }
    }
}

Thuộc tính của đệ quy

Đệ quy có các tính chất sau

1. Nó thực hiện lặp đi lặp lại cùng một nhiệm vụ cho đến khi một điều kiện được đáp ứng
2. Mỗi khi hàm được gọi đệ quy, nó phải được gọi với một bộ đầu vào nhỏ hơn
3. Phải có một trường hợp cơ sở được sử dụng để dừng đệ quy

Cách đệ quy được sử dụng trong lập trình

Đệ quy được triển khai trong các ngôn ngữ lập trình bằng cách sử dụng các hàm. Trong các ngôn ngữ lập trình, hàm là một khối mã được sử dụng để thực hiện một tác vụ cụ thể.

Bất kỳ ngôn ngữ lập trình nào như C, C++, Java, Python, v.v. có thể sử dụng các hàm và triển khai khái niệm về đệ quy .

Chúng ta phải hết sức cẩn thận khi viết hàm đệ quy bằng ngôn ngữ lập trình. Đảm bảo rằng trường hợp cơ sở được viết đúng nếu không nó sẽ gây ra đệ quy vô hạn

điều kiện cơ sở

Trong mọi hàm đệ quy, có một điều kiện cơ sở được sử dụng để dừng đệ quy. Ở điều kiện cơ sở, hàm phải trả về một giá trị cần thiết để giải quyết lệnh gọi hàm trước đó

Giải pháp được chuyển trong ngăn xếp cuộc gọi từ điều kiện cơ sở đến lệnh gọi hàm trước đó và cuối cùng, chúng ta có giải pháp cuối cùng

báo cáo quảng cáo này

Sử dụng bộ nhớ

Khi chức năng chính của chương trình được gọi, bộ nhớ được phân bổ cho chức năng trên ngăn xếp cuộc gọi. Bộ nhớ bị giải phóng khi hàm trả về

Trong trường hợp đệ quy, khi hàm được gọi theo cách đệ quy, hàm mới được phân bổ ở trên cùng của ngăn xếp cuộc gọi. Và điều tương tự xảy ra lặp đi lặp lại cho đến khi điều kiện cơ bản được đáp ứng

Khi chúng tôi đạt đến điều kiện cơ sở, bộ nhớ bắt đầu phân bổ từ đầu ngăn xếp cuộc gọi khi chúng tôi nhận được giá trị trả về của hàm

Việc sử dụng bộ nhớ của đệ quy là O(n) trong đó n là số lần hàm được gọi

• C++
• Java
• con trăn

#include 
using namespace std;

int fib(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fib(n-1) + fib(n-2);
    }
}

int main() {
    int n;
    cin >> n;
    cout << fib(n);
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(fib(n));
    }

    public static int fib(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return fib(n-1) + fib(n-2);
        }
    }
}

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
        
n = int(input())
print(fib(n))

Đệ quy trực tiếp và gián tiếp

Các hàm đệ quy này có thể có hai loại

1. Hàm đệ quy trực tiếp
2. Hàm đệ quy gián tiếp

Hàm đệ quy trực tiếp là hàm gọi chính nó trực tiếp mà không có bất kỳ hàm nào khác gọi nó. Trong khi đó Hàm đệ quy gián tiếp là một hàm gọi một hàm khác gọi chính nó làm cho nó trở thành một hàm đệ quy gián tiếp

Đây là một ví dụ đơn giản để chỉ ra sự khác biệt giữa đệ quy trực tiếp và gián tiếp

// direct recursion
function direct() {
    // code...
    // ...

    // directly calls itself
    direct();
}

// indirect recursion
function indirect() {
    // code...
    // ...

    // call some other function that calls It
    other();
}

function other() {
    // call indirect
    indirect();
}

Đệ quy đuôi và không đuôi

Đệ quy đuôi là một hàm đệ quy được gọi ở cuối lệnh gọi hàm. Đệ quy không đuôi là một hàm đệ quy được gọi khi bắt đầu gọi hàm

Bạn có thể đang nghĩ tại sao cuộc gọi đệ quy được thực hiện ở đâu lại quan trọng như vậy?🤔

Lý do là đệ quy đuôi tốt hơn đệ quy không đuôi. Bởi vì chúng ta biết hàm đệ quy tạo một ngăn xếp khi lời gọi hàm đệ quy là câu lệnh cuối cùng trong hàm, sau đó không cần lưu địa chỉ của nó vào ngăn xếp và nó sẽ được bật ra khỏi ngăn xếp làm cho nó nhanh hơn

Ví dụ về đệ quy

Dưới đây là một số ví dụ về đệ quy

• yếu tố
• Tìm kiếm nhị phân
• Xuôi ngược đều giống nhau
• GCD
• LCM

yếu tố

Giai thừa của một số là tích của tất cả các số từ 1 đến số đó. Ví dụ, giai thừa của 5 là 5 * 4 * 3 * 2 * 1 = 120

Đây là chương trình tìm giai thừa của một số bằng cách sử dụng đệ quy

• C++
• Java
• con trăn

#include 
using namespace std;

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

int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    cout << factorial(n);

    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter a number: ");
        int n = sc.nextInt();
        System.out.println(factorial(n));
    }
    public static int factorial(int n) {
        if (n == 0) {
            return 1;
        } else {
            return n * factorial(n-1);
        }
    }
}

________số 8_______

đầu ra

Enter a number: 5
120

Tìm kiếm nhị phân

Tìm kiếm nhị phân là một thuật toán tìm kiếm hoạt động bằng cách so sánh giá trị của phần tử ở giữa của mảng với giá trị được tìm kiếm. Nếu giá trị nhỏ hơn phần tử ở giữa, thì tìm kiếm tiếp tục ở nửa dưới của mảng. Nếu giá trị lớn hơn phần tử ở giữa, thì tìm kiếm tiếp tục ở nửa trên của mảng. Điều này tiếp tục cho đến khi giá trị được tìm thấy hoặc tìm kiếm kết thúc

Đệ quy trực tiếp và gián tiếp là gì?

Đệ quy trực tiếp là gì?

Các loại đệ quy khác nhau trong Python là gì?

Đệ quy gián tiếp trong lập trình là gì?