[JAVA] 자바 - 재귀 호출

[JAVA]
자바 - 재귀호출

오늘 중요한걸 대체 몇 개를 배웠는지... 클래스로 넘어가면서부터 자바라는 언어를 온전히 받아들이는 과정을 겪는중... 물론 매우 힘들다... 거의 태어나서 처음으로 프로그래밍적인 내용을 배우는 거니까...! 아무튼, 즐.겁.다.

✔️ 재귀호출 이란?

메소드 내에서 메소드 자기 자신을 호출하는 방식!!

영어에 재귀대명사와 같다고 볼 수 있다~

◾ 특징

코드 간결! 오류 수정 용이!

하지만 실행 시간 관점에서 처리 속도가 느려 반복문보다 비효율적이다. 하나 이상의 종료 조건을 두고 꼭! 종료 해야한다.

= 만약 무한반복된다면....  재귀호출은 Stack 영역 사용하기 때문에 java.lang.StackOverflowError 에러 발생하니 주의 ㅠㅠ

◾ 재귀호출 이용한 예시

- 계승 구하기, 하노이 탑, 퀵 정렬, 병합 정렬, 파일 찾기 등...

(개발자 동생이 중요하다고 했음...)

✔️ 재귀호출로 합 구하기

public int sum(int n) {
		return n > 1 ? n+sum(n-1) : n;
					    //스스로 출력 .....쭉..
	}

// n + 재귀 (n-1 + 재귀 (n-2 + 재귀 (n-3 + 재귀 .... 0이 될 때 까지 재귀호출하여 합을 구할 수 있다.

✔️ x의 y승 구하기

개인적으로 조금 이해가 안 갔던 문제 . 어떻게 풀어야하나 감이 오지 않았는데, 위에 재귀호출로 합을 구한 것처럼 삼항 연산자를 이용하면 '어떻게 풀어야할지' 가 보이더라! 삼항 연산자는 익숙하지 않아서 생각해내기 조금 어려웠다.

if (y>=0) {
	return y==0 ? 1: x* pow(x, y-1);
	else
	return (1.0 / x) * pow(x,y+1);

// y가 반복 횟수가 되어준다고 생각하면 편하더라. else 는 x의 -y 승을 구하기 위해서 쓰는데 이번에 배워간다... 수업 시간에 -y승에 대한 지식이 없어서 잘 풀지 못함... 이제 알았으니 됐따!!

✔️ 피보나치 수열

클래스고 메소드고 재귀고 아무것도 모를 때 엄청 고생해서 for 문장으로 풀었는데 '피보나치 수열' 은 재귀호출 쓰니까 순식간에 풀 수 있더라.

public static int fibo (int n) {
	if(n < 2) {
    	return n;
    }
    else if {
    	return fibo(n-1) + fibo(n-2);
        // 0 1 1 2 3 5 ... 
    }
 
}

// 바로 뒤에 두 수를 더해서 만들어지는 피보나치 수열의 원리를 재귀호출로 구현

✔️ 최대공약수 구하기

이번에도 재귀호출 이용하기. 삼항 연산자 이용

public static int gcd(int a, int b) {
	return b==0 ? a : gcd(b, a%b);
}

💡 나머지로 최대공약수 구하는 공식!!!!

a = n1;
b = n2;
		int mod = a % b;
		while (mod > 0) {
			a = b;
			b = mod;
			mod = a % b;
		}

✔️ 트리구조 재귀호출 이해하기...⭐⭐⭐

Test9 t = new Test9();
		t.print(3);
        
        ////////////////////////////
 
class Test9 {
	public void print(int n) {
		System.out.println("start : " + n);
		
		if(n>1) {
			print(n-1);
			print(n-1);
		}
        
		System.out.println("end : " +n);

// 수업 시간에 잠깐 하고 지나갔는데 응? 싶었던 내용이다. 결과는 아래와 같이 나온다.

// start 3 찍고 => n-1 재귀로 돌아감 (n-1 킵)

// start 2 찍고 => 다시 n-1 재귀로 돌아감 (이때, n-1 하나 킵) 

// star 1 찍고 if 거짓, 종료 end 1 찍음

// 2에서 n-1 킵한 것 시작 start 1 + if 거짓으로  end 1

// start 2 드디어 종료 end 2

// 다시 start 3에서 남은 (n-1) 시작

// start 2 찍고 => 다시 n-1 재귀로 돌아감 (이때, n-1 하나 킵)

// start 1 찍고 if 거짓, 종료 end 1 찍음

// 2에서 n-1 킵한 것 시작 start 1 + if 거짓으로 end 1

// start 2 드디어 종료 end 2

// 마지막으로 start 3의 종료 찍음 end 3

느낀점 : 재귀는 정말 뱅글뱅글 모두 호출하여 도는구나......!