Bạn đang xem : Đệ quy java là gì?

Đệ quy là gì?

  • Đệ quy là một quá trình tự gọi phương thức.

Ví dụ:

Ví dụ

1

2

3

4

5

6

7

8

9

void

meth

(

)

{

// một số câu lệnh

meth

(

)

;

// lệnh gọi đệ quy (một phương pháp c alling chính nó)

// một số câu lệnh khác

}

Trong ví dụ trên, một phương thức đang gọi chính nó một cách trực tiếp. Trong một số trường hợp, một phương thức có thể gọi chính nó một cách gián tiếp (thông qua một số phương thức khác).

Ví dụ:

Ví dụ:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

void

meth1

(

)

{

meth2

(

)

;

}

void

meth2

(

)

{

meth1

(

)

;

}

Trong Java, phép đệ quy được phép thông qua các phương thức bình thường nhưng không được phép với các hàm tạo. Vì vậy, đoạn mã sau không hợp lệ (giả sử tên lớp là Kiểm tra, vì vậy tên phương thức khởi tạo cũng là Kiểm tra).

Ví dụ:

Ví dụ về đệ quy Java

1

2

3

4

5

6

7

8

Kiểm tra

(

< p class = "crayon-sy">)

{

this

(

10 < / p>

)

;

}

Kiểm tra

(

int

x

)

{

cái này

(

)

;

}

Ngay cả đệ quy trực tiếp cũng không được phép với các lệnh gọi hàm tạo. Vì vậy, mã sau đây cũng không hợp lệ.

Ví dụ:

Ví dụ

1

2

3

4

5

6

7

Kiểm tra

(

< p class = "crayon-sy">)

{

cái này

(

)

;

}

< / p>

Mặc dù không cho phép đệ quy với lời gọi hàm tạo , chúng ta có thể thực hiện đệ quy với các phương thức bình thường ngay cả khi chúng được khởi tạo tại các hàm tạo. Vì vậy, mã sau đây là hợp lệ.

Ví dụ:

Ví dụ về đệ quy Java

1

2

3

4

5

6

7

8

9

10

11

12

Kiểm tra

(

)

{

meth

(

)

;

}

void

meth

(

)

{

// một số mã

< p class = "crayon-e"> meth

(

)

;

}

Khi đệ quy diễn ra, một phương thức được gọi đi gọi lại. Nếu chúng ta không ngừng lặp lại, thì nó sẽ trở thành những lệnh gọi vô hạn và chương trình không bao giờ kết thúc. Dưới đây là một ví dụ về điều đó.

Ví dụ:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

lớp

Kiểm tra

{

công khai

tĩnh

void

main

(

Chuỗi

arg

[

]

< p class = "crayon-sy">)

{

nums

(

1

)

;

}

< / p>

static

void

< p class = "crayon-e"> nums

(

int

x

)

{< / p>

Hệ thống

.

out

.

in

(

x

+

” ”

)

;

< p class = "crayon-e"> nums

(

x

+

1

)

;

}

}

Đầu ra:

1

1

2

3

4

5

6

…………

.

(

vô thời hạn

)

  • Trong chương trình trên, main () đang gọi nums () với đối số 1.

  • Điều 1 này nói đến phương thức nums () thành x. có 1 được in.

  • Sau đó, nums () tự gọi nó với x + 1 làm đối số.

  • Lần này, nó có nghĩa là 2 được chuyển cho nums () dưới dạng đối số và x nhận 2.

  • Vì vậy, 2 được in và sau đó nums () được gọi với giá trị 3.

Quá trình này tiếp tục mà không có bất kỳ điểm dừng nào. Vì vậy, chương trình tiếp tục thực thi. Nếu chúng ta muốn dừng quá trình thực thi, chúng ta có thể làm như vậy bằng Ctrl + C (từ dấu nhắc lệnh của windows) hoặc chương trình có thể bị kết thúc bởi chính hệ thống vì nó đã trở nên vô hạn (thiếu bộ nhớ).

Đệ quy là một cơ chế rất tốt trong nhiều trường hợp. Tuy nhiên, loại đệ quy (vô hạn) này không hữu ích lắm. Nếu chúng ta có thể điều khiển đệ quy để người lập trình có thể dừng nó (theo cách lập trình / logic / kỹ thuật) tại một điểm mong muốn thì nó sẽ để tốt hơn.

Chương trình trên được viết ở đây với một số sửa đổi để nó dừng lại ở một giai đoạn.

Ví dụ:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

lớp

Kiểm tra

{

công khai

static

void

main

(

Chuỗi

arg

[

]

)

{

< / p>

nums

(

1

)

;

}

static

void

nums

(

int

x

)

< p class = "crayon-h">

{

Hệ thống

.

ra

. < / p>

in

(

x

+

“”

)

;

nếu

(

x

==

3

)

quay lại

;

nums

(

x

+

1

)

;

}

< p class = "crayon-sy">}

Đầu ra:

1

1

2

3

Trong chương trình trên, phương thức nums () có 3 câu lệnh.

  1. out.print (x + ”“);

  2. if (x == 3) trả về;

  3. nums (x + 1);

Khi điều khiển đến với một phương thức, nó sẽ trả về (quay lại) phương thức gọi trong 2 trường hợp.

  1. Khi một câu lệnh trả về được thực thi.

  2. Khi tất cả các câu lệnh trong phương thức được thực thi xong.

Hãy nhớ rằng khi chúng tôi gọi một phương thức một cách đệ quy, cùng một phương thức được gọi nhiều lần và phiên bản đó sẽ được gọi là một phiên bản.

Có nghĩa là, khi nums () được gọi lần đầu tiên, chúng ta hãy tham khảo ở phiên bản đầu tiên và khi phương thức tương tự được gọi lần thứ hai, chúng ta hãy gọi nó là phiên bản thứ hai, v.v.

Lưu ý: Mỗi khi điều khiển có phiên bản mới của một phương pháp, tất cả các biến cục bộ của nó sẽ được tạo mới.

Khi sử dụng đệ quy, chúng ta sẽ thấy hai điều sau đang xảy ra trong phương thức đệ quy.

  1. Một điều kiện kết thúc (để quá trình đệ quy dừng lại)

  2. Chuyển từ giai đoạn bắt đầu sang giai đoạn kết thúc.

Ví dụ trên về in số tự nhiên cũng có thể được viết mà không cần sử dụng đệ quy. Trong trường hợp đó, chúng tôi chỉ sử dụng một cấu trúc lặp / lặp. Cái nào tốt hơn?

Tương tự, chúng ta có thể viết chương trình để in giai thừa của một số theo cách không đệ quy (lặp lại) cũng như theo cách đệ quy. Cái nào tốt hơn?

  • Chúng ta có thể viết một chương trình để tìm GCD của hai số đã cho. Đệ quy tốt hơn hay không đệ quy?

  • Để viết một chương trình sắp xếp nhanh, chúng ta nên chọn gì? Đệ quy hay không đệ quy?

  • đối với sắp xếp hợp nhất, chúng ta nên tiếp cận đệ quy hay không đệ quy?

  • Để đi du lịch một danh sách liên kết theo hướng về phía trước, điều nào tốt hơn?

  • Để in một danh sách liên kết đơn theo hướng ngược lại (từ danh sách cuối cùng đến danh sách đầu tiên), điều gì tốt hơn?

  • Để đi du lịch một cái cây theo thứ tự trước, đặt sau, theo thứ tự và cấp độ, cái nào tốt hơn?

Đối với tất cả những câu hỏi này, chúng ta nên ghi nhớ một nguyên tắc. Nếu chúng ta có thể viết một chương trình mà không có ngăn xếp độc quyền, thì chương trình không đệ quy (lặp lại) sẽ tốt hơn.

Để thay thế cho cách sử dụng (đệ quy hoàn toàn tạo thành một ngăn xếp) độc quyền, chúng ta nên tiếp cận đệ quy. Vì vậy, các chương trình như in các số tự nhiên, giai thừa của một số, GCD của các số, truyền qua danh sách liên kết đơn, truyền đi theo thứ tự cấp cây có thể được thực hiện theo cách không đệ quy.

Tuy nhiên, đệ quy rất hữu ích để viết các chương trình như sắp xếp nhanh, sắp xếp hợp nhất, di chuyển danh sách liên kết đơn theo hướng lùi, sắp xếp trước theo thứ tự sau và theo thứ tự của cây, tháp Hà Nội, truyền qua đồ thị. < / p>

Để tìm giai thừa của một số, chúng ta chỉ có thể sử dụng một vòng lặp và tìm kết quả. Trong trường hợp này, chúng tôi không cần ngăn xếp để lưu trữ dữ liệu trung gian và sau đó sử dụng nó ở giai đoạn sau.

Nhưng để sắp xếp nhanh , chúng tôi cần lưu trữ dữ liệu ở mỗi cấp và sử dụng nó ở giai đoạn sau. Để lưu trữ, chúng tôi cần một ngăn xếp. Vì vậy, chúng ta cũng nên triển khai một ngăn xếp cùng với sắp xếp nhanh. Nếu chúng ta tiếp cận một phương pháp đệ quy, chúng ta không cần phải duy trì một ngăn xếp. Vì vậy, để viết chương trình sắp xếp nhanh, chương trình đệ quy sẽ tốt hơn.

Nếu chúng ta muốn sử dụng nhiều lệnh gọi đệ quy trong một phương thức (một phương thức gọi chính nó nhiều lần) thì cơ chế sẽ hơi phức tạp. Nhưng nó giúp chúng ta giải quyết nhiều vấn đề, nếu không, chúng ta cần viết rất nhiều mã (để duy trì ngăn xếp, đẩy, bật lên, v.v.). Loại phương pháp này được sử dụng trong các phương pháp luận ‘chia để trị’ như sắp xếp nhanh và sắp xếp hợp nhất.

Ví dụ về đệ quy Java với các chương trình mẫu

Ví dụ: 1

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

lớp

RecursionExample1

{

công khai

tĩnh

void

main

(

Chuỗi

args

[

]

)

{

int

i

=

5

;

Đệ quyExample1

.

print

(

i

)

;

}

static

void

print

(

int

i

)

{

if

(

i

& gt;

0

)

{

in

(

i < / p>

1

)

;

Hệ thống

.

< p class = "crayon-v"> ra

.

println

(

i

)

;

< / p>

}

}

< p class = "crayon-line crayon-sọc-line" id = "crayon-62b3cdc849506185139658-20">

}

Đầu ra:

1

2

3

4

5

1

2

3

4

5

Ví dụ: 2

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

lớp

RecursionExample1

{

công khai

tĩnh

void

main

(

Chuỗi

args

[

]

)

{

int

i

=

5

;

RecursionExample1

.

print

(

i

)

;

}

static < / p>

void

print

(

int

i

)

{

if

(

< p class = "crayon-v"> i

& gt;

0

)

{

Hệ thống

.

hết

.

println

(

i

)

;

< / p>

print

(

i

1

)

;

}

}

}

Đầu ra:

1

2

3

4

5

5

4

3

2

1

Nhược điểm / Hạn chế / Nhược điểm của Đệ quy

  • Do quá nhiều lệnh gọi phương thức diễn ra, bộ nhớ được cấp phát cho các biến cục bộ có thể chiếm quá nhiều bộ nhớ.

  • Việc phân bổ tài nguyên cho nhiều phiên bản phương pháp này làm chậm hiệu suất.

  • Một lập trình viên bình thường cảm thấy khó hiểu hoạt động của đệ quy.


Xem thêm những thông tin liên quan đến chủ đề java đệ quy là gì

Cấu trúc dữ liệu & Giải thuật [06]: Đệ quy – #Recursion

  • Tác giả: The Brown Box
  • Ngày đăng: 2020-08-15
  • Đánh giá: 4 ⭐ ( 2799 lượt đánh giá )
  • Khớp với kết quả tìm kiếm: 🔥 Ưu đãi 75% khóa học: https://courses.hoangvancong.com/
    🔥 Group giải LeetCode DÀNH RIÊNG cho học viên: https://bit.ly/3fmDBKI
    🔥 Lớp học OFFLINE tại Techmaster: https://techmaster.vn/khoa-hoc/j79/java-cau-truc-du-lieu-giai-thuat

    [DataStructure&Algorithm][06]: Recursion – Đệ quy (recursion)

    Danh sách các bài sử dụng đệ quy:
    * Ứng dụng chung:
    +) Day 34: https://youtu.be/SEtxn9UPIW4

    +) Day 35: https://youtu.be/JOixabUWrBQ
    +) Day 36: https://youtu.be/Cz9N-289VC8
    +) Day 37: https://www.youtube.com/watch?v=B6mgXhAU_f4
    +) Day 38: https://youtu.be/XF6MyehncDw
    +) Day 39: https://youtu.be/lgCwEYJVuUc

    * Ứng dụng trong thuật toán sắp xếp:

    * Ứng dụng trong Searching (Tìm kiếm):

    * Ứng dụng trong Linked List (Danh sách liên kết):

    * Ứng dụng trong Binary Tree và Binary Search Tree (Cây nhị phân và Cây nhị phân Tìm kiếm):

    ===============================================================
    +) Daily LeetCode Challenge: https://www.youtube.com/playlist?list=PLqLksqdSk4b37pGIyfy_266wP0-S68HDh
    FB: https://www.facebook.com/thebrownboxfb
    Blog: http://www.hoangvancong.com

    Khoá học Cấu Trúc Dữ Liệu và Giải Thuật: [Sắp ra mắt]

    ======================== Giới Thiệu =============================

    Data Structure & Algorithm

    Đây là chuỗi video được thực hiện song song với series “Daily LeetCode Challenge” nhằm mục đích cung cấp cho các bạn các kiến thức cơ bản về cấu trúc dữ liệu và giải thuật, từ đó mà có cơ sở để thực hiện các bài tập trong series đó.

    Nội dung series bao gồm:
    – Cấu trúc dữ liệu:
    + Array – Mảng
    + Stack & Queue – Ngăn xếp & Hàng đợi
    + Linked List – Danh sách liên kết
    + Binary Tree
    + Binary Search Tree
    + Trie
    + Hash Table

    – Giải thuật:
    + Các giải thuật sắp xếp
    + Quick sort
    + Tìm kiếm
    + Đệ quy
    + BFS: Breadth First Search – Tìm kiếm theo chiều rộng
    + DFS: Depth First Search – Tìm kiếm theo chiều sâu
    + Các thuật toán trên đồ thị

    datastructure algorithm
    Tags: The Brown Box, hoangvancong.com, cau truc du lieu va giai thuat, data structure, algorithm, data structure and algorithm, daily leetcode challenge, leetcode

    =====================================================

    Music:
    Brandenburg Concerto No4-1 BWV1049 – Classical Whimsical của Kevin MacLeod được cấp phép theo giấy phép Creative Commons Attribution (https://creativecommons.org/licenses/by/4.0/)
    Nguồn: http://incompetech.com/music/royalty-free/index.html?isrc=USUAN1100303
    Nghệ sĩ: http://incompetech.com/

Đệ quy trong java

  • Tác giả: viettuts.vn
  • Đánh giá: 3 ⭐ ( 8256 lượt đánh giá )
  • Khớp với kết quả tìm kiếm: Đệ quy trong java là quá trình trong đó một phương thức gọi lại chính nó liên tiếp. Một phương thức trong java gọi lại chính nó gọi là phương thức đệ quy.

Đệ quy trong Java (bất kỳ ngôn ngữ lập trình nào)

  • Tác giả: teamvietdev.com
  • Đánh giá: 5 ⭐ ( 7401 lượt đánh giá )
  • Khớp với kết quả tìm kiếm:

Đệ Quy Siêu Cơ Bản Cho Người Mới Bắt Đầu

  • Tác giả: codelearn.io
  • Đánh giá: 4 ⭐ ( 3271 lượt đánh giá )
  • Khớp với kết quả tìm kiếm: Đệ quy là một khái niệm khá cơ bản trong lập trình, bài viết này mình sẽ giải thích về đệ quy và những khái niệm liên quan đến nó nhé.

reverse List trong Java sử dụng đệ quy

  • Tác giả: viblo.asia
  • Đánh giá: 4 ⭐ ( 6912 lượt đánh giá )
  • Khớp với kết quả tìm kiếm: Nếu bạn đã từng cần phải reverse một List trong Java, chắc hẳn bạn đã nghe đến phương thức Collections.reverse(). Điều đầu tiên, mình lưu ý là nên sử dụng phương thức này cho các trường hợp mà bạn cần…

[Tự học Java] Kỹ thuật đệ quy(recursion) trong Java

  • Tác giả: cafedev.vn
  • Đánh giá: 4 ⭐ ( 6530 lượt đánh giá )
  • Khớp với kết quả tìm kiếm: Trong bài viết này, bạn sẽ tìm hiểu cách để tạo ra hàm đệ quy (recursive function), một hàm mà tự gọi chính nó. Đồng thời, bạn cũng sẽ tìm hiểu thêm về điểm thuận lợi và điểm bất lợi của chúng.

Lập Trình Từ Đầu

  • Tác giả: laptrinhtudau.com
  • Đánh giá: 4 ⭐ ( 3633 lượt đánh giá )
  • Khớp với kết quả tìm kiếm: Đệ quy trong Java – Lập Trình Từ Đầu 5 Hàm-Phương Thức Trong JAVA

Xem thêm các bài viết khác thuộc chuyên mục: Kiến thức lập trình

Xem Thêm  Hình ảnh tạo kiểu CSS - hình ảnh biểu ngữ html css

By ads_php