recursion java tutorial with examples
Java의 재귀에 대한이 심층 자습서에서는 예제, 유형 및 관련 개념을 사용하여 재귀가 무엇인지 설명합니다. 또한 재귀 대 반복도 다룹니다.
Java의 이전 자습서에서 루프를 선언 한 다음 한 번에 하나의 요소를 가져 와서 반복적 인 방식으로 데이터 구조를 탐색하는 반복적 인 접근 방식을 보았습니다.
우리는 또한 하나의 루프 변수를 유지하고 루프 변수가 조건을 충족 할 때까지 코드 조각을 반복하는 조건부 흐름을 보았습니다. 함수 호출과 관련하여 우리는 함수 호출에 대한 반복적 인 접근 방식도 탐구했습니다.
이 튜토리얼에서는 프로그래밍에 대한 다른 접근 방식, 즉 재귀 접근 방식에 대해 설명합니다.
학습 내용 :
Java에서 재귀 란 무엇입니까?
재귀는 함수 나 메서드가 자신을 반복해서 호출하는 프로세스입니다. 직접 또는 간접적으로 반복해서 호출되는이 함수를 '재귀 함수'라고합니다.
재귀를 이해하기 위해 다양한 예제를 볼 것입니다. 이제 재귀 구문을 살펴 보겠습니다.
재귀 구문
Recursion을 구현하는 모든 메서드에는 두 가지 기본 부분이 있습니다.
- 자신을 호출 할 수있는 메서드 호출, 즉 재귀
- 재귀를 중지하는 전제 조건입니다.
재귀 메서드에는 전제 조건이 필요합니다. 재귀를 중단하지 않으면 무한히 계속 실행되어 스택 오버플로가 발생하기 때문입니다.
재귀의 일반적인 구문은 다음과 같습니다.
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } 전제 조건은 기본 조건이라고도합니다. 다음 섹션에서 기본 조건에 대해 자세히 설명합니다.
자바의 재귀 이해
이 섹션에서는 재귀 프로세스를 이해하고 어떻게 발생하는지 살펴 보겠습니다. 기본 조건, 스택 오버플로에 대해 배우고 재귀 및 기타 세부 사항을 통해 특정 문제를 해결하는 방법을 알아 봅니다.
재귀 기준 조건
재귀 프로그램을 작성하는 동안 먼저 기본 사례에 대한 솔루션을 제공해야합니다. 그런 다음 더 작은 문제로 더 큰 문제를 표현합니다.
로 예, 우리는 숫자의 계승을 계산하는 고전적인 문제를 취할 수 있습니다. n이 주어지면 n으로 표시된 n의 계승을 찾아야합니다!
이제 재귀를 사용하여 n 계승 (n!)을 계산하는 프로그램을 구현해 보겠습니다.
public class Main{ static int fact(int n) { if (n == 1) // base condition return 1; else return n*fact(n-1); } public static void main(String() args) { int result = fact(10); System.out.println('10! = ' + result); } }산출
이 프로그램에서 우리는 조건 (n<=1) is the base condition and when this condition is reached, the function returns 1. The else part of the function is the recursive call. But every time the recursive method is called, n is decremented by 1.
따라서 궁극적으로 n의 값은 1 또는 1 미만이 될 것이며이 시점에서 메서드는 값 1을 반환 할 것이라는 결론을 내릴 수 있습니다.이 기본 조건에 도달하고 함수가 중지됩니다. n의 값은 기본 조건을 충족하는 한 무엇이든 될 수 있습니다.
재귀를 사용한 문제 해결
재귀 사용의 기본 개념은 더 작은 문제로 더 큰 문제를 표현하는 것입니다. 또한 재귀에서 벗어날 수 있도록 하나 이상의 기본 조건을 추가해야합니다.
이것은 위의 팩토리얼 예제에서 이미 입증되었습니다. 이 프로그램에서 우리는 더 작은 값으로 n 개의 계승 (n!)을 표현했고 기본 조건 (n<=1) so that when n reaches 1, we can quit the recursive method.
재귀의 스택 오버플로 오류
메서드 나 함수가 호출 될 때 함수의 상태가 스택에 저장되고 함수가 반환 될 때 검색된다는 것을 알고 있습니다. 스택은 재귀 적 방법에도 사용됩니다.
그러나 재귀의 경우 기본 조건을 정의하지 않거나 기본 조건에 도달하거나 실행되지 않으면 문제가 발생할 수 있습니다. 이 상황이 발생하면 스택 오버플로가 발생할 수 있습니다.
아래의 계승 표기법 예를 살펴 보겠습니다.
여기서 우리는 잘못된 기본 조건, n == 100을 지정했습니다.
public class Main { static int fact(int n) { if (n == 100) // base condition resulting in stack overflow return 1; else return n*fact(n-1); } public static void main(String() args) { int result = fact(10); System.out.println('10! = ' + result); } }따라서 n> 100이면 메서드는 1을 반환하지만 재귀는 중지되지 않습니다. n의 값은 중지 할 다른 조건이 없기 때문에 무한정 계속 감소합니다. 이것은 스택이 오버플로 될 때까지 계속됩니다.
또 다른 경우는 n의 값이<100. In this case, as well the method will never execute the base condition and result in a stack overflow.
자바의 재귀 예제
이 섹션에서는 재귀를 사용하여 다음 예제를 구현합니다.
# 1) 재귀를 사용한 피보나치 시리즈
피보나치 시리즈는 다음과 같이 주어집니다.
1,1,2,3,5,8,13,21,34,55, ...
위의 시퀀스는 현재 요소가 이전 두 요소의 합임을 보여줍니다. 또한 피보나치 수열의 첫 번째 요소는 1입니다.
따라서 일반적으로 n이 현재 숫자이면 (n-1)과 (n-2)의 합으로 주어집니다. 현재 요소를 이전 요소로 표현하므로 재귀를 사용하여이 문제를 표현할 수 있습니다.
피보나치 시리즈를 구현하는 프로그램은 다음과 같습니다.
public class Main { //method to calculate fibonacci series static int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); } public static void main(String() args) { int number = 10; //print first 10 numbers of fibonacci series System.out.println ('Fibonacci Series: First 10 numbers:'); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + ' '); } } } 산출
# 2) 재귀를 사용하여 숫자가 회문인지 확인
회문은 왼쪽에서 오른쪽으로 또는 오른쪽에서 왼쪽으로 읽을 때 동일한 순서입니다.
121이라는 숫자가 주어지면 왼쪽에서 오른쪽으로, 오른쪽에서 왼쪽으로 읽을 때 동일하다는 것을 알 수 있습니다. 따라서 번호 121은 회문입니다.
다른 숫자 1242를 봅시다. 왼쪽에서 오른쪽으로 읽으면 1242이고 오른쪽에서 왼쪽으로 읽으면 2421입니다. 따라서 이것은 회문이 아닙니다.
우리는 숫자의 자릿수를 반전하여 회문 프로그램을 구현하고 주어진 숫자를 반전 된 표현과 재귀 적으로 비교합니다.
아래 프로그램은 회문을 확인하는 프로그램을 구현합니다.
import java.io.*; import java.util.*; public class Main { // check if num contains only one digit public static int oneDigit(int num) { if ((num >= 0) && (num <10)) return 1; else return 0; } //palindrome utility function public static int isPalindrome_util (int num, int revNum) throws Exception { // base condition; return if num=0 if (num == 0) { return revNum; } else { //call utility function recursively revNum = isPalindrome_util(num / 10, revNum); } // Check if first digit of num and revNum are equal if (num % 10 == revNum % 10) { // if yes, revNum will move with num return revNum / 10; } else { // exit throw new Exception(); } } //method to check if a given number is palindrome using palindrome utility function public static int isPalindrome(int num) throws Exception { if (num < 0) num = (-num); int revNum = (num); return isPalindrome_util(num, revNum); } public static void main(String args()) { int n = 1242; try { isPalindrome(n); System.out.println('Yes, the given number ' + n + ' is a palindrome.'); } catch (Exception e) { System.out.println('No, the given number ' + n + ' is not a palindrome.'); } n = 1221; try { isPalindrome(n); System.out.println('Yes, the given number ' + n + ' is a palindrome.'); } catch (Exception e) { System.out.println('No, the given number ' + n + ' is not a palindrome.'); } } }산출
# 3) 역 문자열 재귀 자바
문자열 'Hello'가 주어지면 결과 문자열이 'olleH'가되도록 반전해야합니다.
이것은 재귀를 사용하여 수행됩니다. 문자열의 마지막 문자부터 시작하여 문자열의 모든 문자가 소진 될 때까지 각 문자를 재귀 적으로 인쇄합니다.
아래 프로그램은 재귀를 사용하여 주어진 문자열을 뒤집습니다.
class String_Reverse { //recursive method to reverse a given string void reverseString(String str) { //base condition; return if string is null or with 1 or less character if ((str==null)||(str.length() <= 1)) System.out.println(str); else { //recursively print each character in the string from the end System.out.print(str.charAt(str.length()-1)); reverseString(str.substring(0,str.length()-1)); } } } class Main{ public static void main(String() args) { String inputstr = 'SoftwareTestingHelp'; System.out.println('The given string: ' + inputstr); String_Reverse obj = new String_Reverse(); System.out.print('The reversed string: '); obj.reverseString(inputstr); } } 산출
soapui 인터뷰 질문 및 답변 doc
# 4) 바이너리 검색 자바 재귀
이진 검색 알고리즘은 검색을위한 유명한 알고리즘입니다. 이 알고리즘에서 정렬 된 n 개의 요소 배열이 주어지면이 배열에서 주어진 키 요소를 검색합니다. 처음에는 배열의 중간 요소를 찾아서 배열을 두 부분으로 나눕니다.
그런 다음 키 중간 여부에 따라 배열의 전반부 또는 후반부에서 검색을 제한합니다. 이렇게하면 핵심 요소의 위치를 찾을 때까지 동일한 프로세스가 반복됩니다.
여기서 재귀를 사용하여이 알고리즘을 구현합니다.
import java.util.*; class Binary_Search { // recursive binary search int binarySearch(int numArray(), int left, int right, int key) { if (right >= left) { //calculate mid of the array int mid = left + (right - left) / 2; // if the key is at mid, return mid if (numArray(mid) == key) return mid; // if key key) return binarySearch(numArray, left, mid - 1, key); // Else recursively search in the right subarray return binarySearch(numArray, mid + 1, right, key); } // no elements in the array, return -1 return -1; } } class Main{ public static void main(String args()) { Binary_Search ob = new Binary_Search(); //declare and print the array int numArray() = { 4,6,12,16,22}; System.out.println('The given array : ' + Arrays.toString(numArray)); int len = numArray.length; //length of the array int key = 16; //key to be searched int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println('Element ' + key + ' not present'); else System.out.println('Element ' + key + ' found at index ' + result); } } 산출
# 5) 재귀를 사용하여 배열에서 최소값 찾기
재귀를 사용하여 배열에서 최소값을 찾을 수도 있습니다.
배열에서 최소값을 찾는 Java 프로그램은 다음과 같습니다.
import java.util.*; class Main { static int getMin(int numArray(), int i, int n) { //return first element if only one element or minimum of the array elements return (n == 1) ? numArray(i) : Math.min(numArray(i), getMin(numArray,i + 1 , n - 1)); } public static void main(String() args) { int numArray() = { 7,32,64,2,10,23 }; System.out.println('Given Array : ' + Arrays.toString(numArray)); int n = numArray.length; System.out.print('Minimum element of array: ' + getMin(numArray, 0, n) + '
'); } }산출
다음은 재귀의 몇 가지 예입니다. 이러한 예 외에도 소프트웨어의 다른 많은 문제는 재귀 기술을 사용하여 구현할 수 있습니다.
재귀 유형
재귀는 재귀 메서드를 호출하는시기에 따라 두 가지 유형이 있습니다.
그들은:
# 1) 꼬리 재귀
재귀 메소드에 대한 호출이 재귀 메소드 내에서 실행 된 마지막 명령문 일 때이를 'Tail Recursion'이라고합니다.
꼬리 재귀에서 재귀 호출 문은 일반적으로 메서드의 반환 문과 함께 실행됩니다.
꼬리 재귀의 일반적인 구문은 다음과 같습니다.
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } # 2) 머리 재귀
머리 재귀는 꼬리 재귀가 아닌 모든 재귀 접근 방식입니다. 그래서 일반적인 재귀조차도 재귀를 앞두고 있습니다.
헤드 재귀 구문은 다음과 같습니다.
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } 자바에서 재귀 대 반복
| 재귀 | 되풀이 |
|---|---|
| 시간 복잡성이 매우 높습니다. | 시간 복잡성은 상대적으로 낮은 편입니다. |
| 재귀는 기본 조건이 충족 될 때까지 메서드가 자신을 반복적으로 호출하는 프로세스입니다. | 반복은 코드 조각이 유한 횟수 동안 또는 조건이 충족 될 때까지 반복적으로 실행되는 프로세스입니다. |
| 기능에 대한 응용 프로그램입니다. | 루프에 적용 가능합니다. |
| 더 작은 코드 크기에 적합합니다. | 더 큰 코드 크기에 적합합니다. |
| 각 재귀 호출이 스택으로 푸시 될 때 더 많은 메모리를 사용합니다. | 비교적 적은 메모리가 사용됩니다. |
| 디버그 및 유지 관리가 어려움 | 디버그 및 유지 관리가 더 쉬움 |
| 기본 조건이 지정되지 않거나 도달하지 않으면 스택 오버플로가 발생합니다. | 무한히 실행할 수 있지만 궁극적으로 메모리 오류로 실행을 중지합니다. |
자주 묻는 질문
Q # 1) Java에서 재귀는 어떻게 작동합니까?
대답: 재귀에서 재귀 함수는 기본 조건이 충족 될 때까지 반복적으로 자신을 호출합니다. 호출 된 함수의 메모리는 호출 함수의 메모리 맨 위에있는 스택으로 푸시됩니다. 각 함수 호출에 대해 지역 변수의 별도 사본이 만들어집니다.
질문 # 2) 재귀가 사용되는 이유는 무엇입니까?
대답: 재귀는 더 작은 문제로 나눌 수있는 문제를 해결하는 데 사용되며 전체 문제를 더 작은 문제로 표현할 수 있습니다.
반복적 인 접근 방식을 사용하여 해결하기에는 너무 복잡한 문제에도 재귀가 사용됩니다. 시간 복잡성이 문제가되지 않는 문제 외에도 재귀를 사용하십시오.
질문 # 3) 재귀의 이점은 무엇입니까?
대답:
재귀의 이점은 다음과 같습니다.
- 재귀는 함수의 중복 호출을 줄입니다.
- 재귀를 사용하면 반복적 인 접근 방식과 비교할 때 문제를 쉽게 해결할 수 있습니다.
Q # 4) 재귀 또는 반복 중 어느 것이 더 낫습니까?
대답: 재귀는 기본 함수에 도달 할 때까지 반복 호출을합니다. 따라서 각 함수 호출에 대한 메모리가 스택으로 푸시되므로 메모리 오버 헤드가 발생합니다.
반면 반복은 메모리 오버 헤드가 많지 않습니다. 재귀 실행은 반복적 인 접근 방식보다 느립니다. 재귀는 코드의 크기를 줄이는 반면 반복적 인 접근 방식은 코드를 크게 만듭니다.
질문 # 5) 반복보다 재귀의 장점은 무엇입니까?
대답:
- 재귀는 코드를 더 명확하고 짧게 만듭니다.
- 재귀는 하노이 타워, 트리 순회 등과 같은 문제에 대한 반복적 인 접근 방식보다 낫습니다.
- 모든 함수 호출에는 메모리가 스택에 푸시되므로 Recursion은 더 많은 메모리를 사용합니다.
- 재귀 성능은 반복적 접근 방식보다 느립니다.
결론
재귀는 프로그래밍 언어에 관계없이 소프트웨어에서 매우 중요한 개념입니다. 재귀는 주로 하노이의 탑, 트리 순회, 연결 목록 등과 같은 데이터 구조 문제를 해결하는 데 사용됩니다. 더 많은 메모리가 필요하지만 재귀는 코드를 더 간단하고 명확하게 만듭니다.
이 튜토리얼에서 재귀에 대한 모든 것을 살펴 보았습니다. 또한 개념을 더 잘 이해하기 위해 수많은 프로그래밍 예제를 구현했습니다.
추천 도서
- C ++의 재귀
- Java Iterator : 예제를 통해 Java에서 반복자를 사용하는 방법 배우기
- 예제가있는 Java의 ListIterator 인터페이스
- 초보자를위한 JAVA 튜토리얼 : 100 개 이상의 실습 Java 비디오 튜토리얼
- 프로그램 예제가 포함 된 Java For 루프 자습서
- Java While 루프-프로그래밍 예제가 포함 된 자습서
- Java Do While 루프-예제가 포함 된 튜토리얼
- 자바의 들쭉날쭉 한 배열-예제가있는 자습서