Hàm lũy thừa đệ quy c++

Đệ quy là một khái niệm toán học và lập trình phổ biến. Nó có nghĩa là một chức năng gọi chính nó. Điều này có lợi là bạn có thể lặp qua dữ liệu để đạt được kết quả

Nhà phát triển nên rất cẩn thận với đệ quy vì có thể khá dễ dàng viết một hàm không bao giờ kết thúc hoặc một hàm sử dụng quá nhiều bộ nhớ hoặc sức mạnh của bộ xử lý. Tuy nhiên, khi được viết đúng, đệ quy có thể là một cách tiếp cận lập trình rất hiệu quả và thanh lịch về mặt toán học.

Trong ví dụ này, tri_recursion() là một hàm mà chúng ta đã xác định để gọi chính nó ("recurse"). Chúng tôi sử dụng biến k làm dữ liệu, giá trị này giảm (-1) mỗi khi chúng tôi lặp lại. Đệ quy kết thúc khi điều kiện không lớn hơn 0 (i. e. khi nó bằng 0)

Đối với một nhà phát triển mới, có thể mất một chút thời gian để tìm ra chính xác cách thức hoạt động của nó, cách tốt nhất để tìm hiểu là thử nghiệm và sửa đổi nó

Viết chương trình C để nhập một số từ người dùng và tìm lũy thừa của số đã cho bằng cách sử dụng đệ quy. Cách tìm lũy thừa của một số bằng hàm đệ quy trong lập trình C. Logic tìm lũy thừa của một số sử dụng đệ quy trong lập trình C

Thí dụ

Đầu vào

Input base number: 5
Input power: 2

đầu ra

2 ^ 5 = 25

Kiến thức cần thiết

Lập trình C căn bản, If other, Hàm, Đệ quy

Phải biết -

• Chương trình tìm nguồn sử dụng vòng lặp
• Chương trình tìm nguồn sử dụng hàm pow()

Khai báo hàm đệ quy tìm lũy thừa

Trên đây là định nghĩa toán học của hàm đệ quy tìm lũy thừa của một số. Hàm chấp nhận hai số i. e. x và y và tính toán x ^ y

Bây giờ chúng ta hãy biến đổi hàm toán học trên trong ngữ cảnh lập trình C

1. Trước tiên hãy đặt một cái tên có ý nghĩa cho hàm đệ quy của chúng ta, nói pow()
2. Hàm phải chấp nhận hai số i. e. cơ số và số mũ và tính lũy thừa của nó. Do đó, lấy hai tham số cho cơ số và số mũ, giả sử pow(double base, int exponent);
3. Cuối cùng hàm sẽ trả về base ^ exponent i. e. một giá trị loại double

Khai báo hàm cuối cùng để tính công suất là – double pow(double base, int exponent);

xu hướng

Phân loại ngôn ngữ lập trình

Logic để tính lũy thừa của một số bằng cách sử dụng đệ quy

Sau khi khai báo hàm pow(), đã đến lúc xác định logic để tìm năng lượng theo cách đệ quy. Có thể xảy ra ba trường hợp khi tính lũy thừa của một số

Hiểu hàm số mũ

Ở đây, đầu tiên, chúng ta sẽ nói về hàm số mũ i. e. mn đang tăng m lên n lần đang nhân m lên n lần. Dưới đây là biểu thức toán học của công suất

Ta có hai cách định nghĩa hàm đệ quy lũy thừa như sau

1. Phương pháp đầu tiên yêu cầu nhiều phép nhân hơn
2. Phương pháp thứ hai yêu cầu số phép nhân ít hơn

Phương pháp 1

Trong ví dụ sau, chúng tôi đã tạo một hàm pow nhận hai tham số v (số) và e (số mũ). Trong bước tiếp theo, chúng tôi xác định điều kiện cơ sở của mình (nơi hàm kết thúc hoặc kết thúc), đó là nếu e == 0. Nếu thỏa mãn thì trả về 1 nếu không thì trả về pow(v, e – 1) * v

Trong hàm pow này, giá trị sẽ được trả về tại thời điểm trả về từ các cuộc gọi đệ quy. Chức năng này sẽ kết thúc tại e == 0. Và khi kết thúc, nó trả về 1, từ đó nó bắt đầu nhân 1 này với tham số hàm v, i. e. , 2*2*2*2. Và theo cách này, hàm đệ quy pow của chúng ta sẽ tính toán số mũ của giá trị đã cho. Nếu điều này không rõ ràng vào lúc này, đừng lo lắng khi chúng ta thảo luận về cây theo dõi của ví dụ này, thì chắc chắn bạn hiểu hàm đệ quy này

Tracing Tree của chương trình trên

Bây giờ, hãy nhảy vào Tracing Tree, nơi chúng ta sẽ hiểu từng bước

Bước 1

Cây – Trong sơ đồ trên, có 5 bước. Trong mỗi bước, chúng tôi đã chỉ ra mọi lệnh gọi đệ quy của hàm pow. Như thể hiện trong sơ đồ, chúng tôi đã chuyển 2 và 4 làm tham số

1. Ở bước đầu tiên, nó kiểm tra xem 4 == 0? . Ở đây chúng ta không thể thực hiện phép nhân, đầu tiên nó phải thực hiện lệnh pow (2, 4 – 1) xong thì mới thực hiện phép nhân
2. Ở bước thứ 2, nó kiểm tra xem 3 == 0? . Ở đây cũng vậy, trước tiên chúng ta sẽ phải tính kết quả của cuộc gọi pow (2, 3 – 1) sau đó chỉ phép nhân sẽ thực hiện
3. Ở bước thứ 3, nó kiểm tra xem 2 == 0? . trước tiên chúng ta sẽ phải tính kết quả của lệnh gọi pow (2, 2 – 1) sau đó chỉ phép nhân sẽ thực hiện
4. Ở bước thứ 4, nó kiểm tra xem 1 == 0? . trước tiên chúng ta sẽ phải tính kết quả của lệnh gọi pow (2, 1 – 1) sau đó chỉ phép nhân sẽ thực hiện
5. Ở bước thứ 5, nó kiểm tra xem 0 == 0? . Và từ đây phép nhân bắt đầu, trả về thời gian từ các cuộc gọi đệ quy. Bây giờ, nó sẽ nhân kết quả của mỗi lệnh gọi đệ quy với 2 và ở lệnh gọi cuối cùng, nó sẽ trả về giá trị pow được tính toán của giá trị đã cho

Bước 2

Cây – Bây giờ như chúng ta đã thảo luận ở bước trước khi điều kiện cơ sở (e == 0) đúng thì nó sẽ trả về 1. Và 1 này sẽ quay lại lời gọi trước đó và được nhân với giá trị đã cho của v(2) như trong sơ đồ, ở đây kết quả của phép nhân là 1, tiếp tục quay lại lời gọi đệ quy trước đó. Ở đây, giá trị nhân là 2, trả về lệnh gọi pow (2, 1)

Bước 3

Cây – Bây giờ giá trị nhân là 4, giá trị này trả về lệnh gọi pow (2, 2) và được nhân thêm với giá trị của v i. e. , 2

Bước 4

Cây - Bây giờ ở đây, phép nhân diễn ra trong khoảng từ 4 đến 2 và giá trị được tính là 8 sẽ trả về lệnh gọi pow (2, 3)

Bước5

Cây – Bây giờ giá trị tính toán cuối cùng là 16 mà pow (2, 4) trả về vị trí mà chúng ta đã gọi giá trị này bên trong hàm chính. Trong ví dụ hiện tại của chúng tôi, chúng tôi gọi hàm này trong câu lệnh in. Bây giờ, khi hàm trả về giá trị cuối cùng, nó sẽ in ra màn hình đầu ra

Hoàn thành mã

#include 
int power(int v, int e) {
    if (e == 0)
       return 1;
    return power(v, e - 1) * v;
}

int main() {
    int v = 2, e = 4;
    printf("%d", power(v, e));
}

đầu ra. 16

Thời gian phức tạp. Ô(e)

Ghi chú. Tổng số phép nhân đã thực hiện. lần điện tử

Phương pháp 2

Chúng tôi sẽ sửa đổi hàm đệ quy trước đó để nó tính toán với số phép nhân ít hơn. Sau đó, chức năng mất ít thời gian hơn và ít bộ nhớ hơn trong ngăn xếp. Chúng ta có thể viết 24 là 24 = (22)2. Câu lệnh trên nêu rõ nếu chúng ta thực hiện một phép nhân trên cùng một giá trị thì công suất sẽ giảm đi một nửa. Và giả sử chúng ta có 29 thì chúng ta có thể viết nó là 29 = 2 * (22)4

Trong biểu thức trên, số mũ của 2 là số lẻ là 9. Vì vậy, trong tình huống này, chúng tôi tách một 2 và sau đó một nửa sức mạnh. Vì vậy, có thể có hai điều kiện

1. Nếu sức mạnh là chẵn - thì trực tiếp một nửa sức mạnh
2. Nếu lũy thừa là số lẻ – thì trước tiên hãy tách một giá trị khỏi lũy thừa và cộng vào phép nhân với số đó, sau đó lấy một nửa lũy thừa

Đoạn mã sau thực hiện hai điều trên

Tracing Tree của chương trình đệ quy trên

Bây giờ, hãy nhảy vào Tracing Tree, nơi chúng ta sẽ hiểu từng bước

Bước 1

Cây. Chúng tôi chuyển 2 dưới dạng số và 9 dưới dạng số mũ trong hàm pow. Sau đó, nó kiểm tra điều kiện cơ sở của nó là nếu 9 == 0?

Bước 2

Cây. Ở đây nó kiểm tra điều kiện cơ sở của nó là nếu 4 == 0?

Bước 3

Cây. Ở đây nó kiểm tra điều kiện cơ bản của nó là nếu 2 == 0?

Bước 4

Cây. Nó kiểm tra điều kiện cơ bản nếu 1 == 0?

Bước5

Cây. Trong bước trước của chúng tôi, 1 được trả về pow (28, 1). Từ cuộc gọi này 28 * 1 sẽ trở lại pow (24, 2). Vì không có phép nhân đang chờ xử lý nên điều này cũng trả về 28 * 1 cho pow (22, 4)

Bước 6

Cây. Ở bước trước của chúng ta, 28 * 1 đến pow (22, 4). Bây giờ, đây là phép nhân đang chờ xử lý là 2 * thành pow (22, 4). Và điều này sẽ trả về 2 * 28 * 1 cho pow (2, 9). Giá trị tính toán cuối cùng là 29 là 512

Phương pháp trên yêu cầu số phép nhân ít hơn so với phương pháp đệ quy trước đó

Hoàn thành mã

#include 
int power(int v, int e) {
    if (e == 0)
        return 1;
    if (e % 2 == 0)
       return power(v * v, e / 2);
    return v * power(v * v, (e - 1) / 2);
}

int main() {
    int x = 2, v = 9;
    printf("%d", power(x, v));
}

đầu ra. 512

Trong bài viết tiếp theo, tôi sẽ thảo luận về chuỗi Taylor bằng cách sử dụng đệ quy trong ngôn ngữ C với ví dụ. Ở đây, trong bài viết này, tôi cố gắng giải thích Luỹ thừa của một số đã cho bằng Ngôn ngữ C bằng cách sử dụng Đệ quy kèm theo ví dụ và tôi hy vọng bạn thích bài viết Luỹ thừa của một số đã cho bằng cách sử dụng Đệ quy bằng Ngôn ngữ C kèm theo ví dụ