Đệ 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

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  n;
    cout