Recursion1 (재귀 기초)

2020-01-06

1. 문자열 재귀로 하나씩 출력하기

public class Solution {

    static void ja(String a) {
	if(a.length() == 0)
		return ;

	else {
		System.out.println(a.charAt(0));
		ja(a.substring(1));
	}

}

    public static void main(String[] args) {
        ja("hello world!");
    }
}



2. 문자열 반대로 출력하기

public class Solution {


	static void ja(String a) {
		if(a.length() == 0)
			return ;

		else {
			System.out.println(a.charAt(a.length()-1));
			ja(a.substring(0, a.length()-1));
		}

	}


	public static void main(String[] args) {
		ja("hello world!");
	}

}

* 기저조건에서 return 0; 으로 끝내기때문에 돌아가지않고 ->->->안으로 따라들어가고 끝남 (for문과 비슷하게 작동)



3. 최대공약수 구하기 (by 유클리드호제법)

	static int sol(int m, int n) {
		// m >= n 라고 가정
		if(m%n == 0)
			return n; //나뉘어 떨어지면 n의 배수가 m이라는 얘기니까 n자체가 최대공약수
		else
			return sol(n, m%n); // ->->->들어갔다가 if에 걸린 n값이 return으로 돌아옴

	}


	public static void main(String[] args) {
		System.out.println(sol(15,10));
	}



  • 유클리드 호제법

    m>=n 일때 (m,n)의 최대공약수는 (n,m%n)과 같다.

  • 기저조건이 if문이고 아무리 큰 수도 else를 타고 가다보면 if를 만나고

    1) 그전에 배수가 되는걸 만나면 n return

    2)나누다보면 나머지는 제일 작은 1이 되기때문에 1 return

    -> 결국은 기저조건에서 만나는 n or 1이라는 같은 값을 계속 올라오면서 return




4. 2진수 출력하기

public class Solution {

	static void sol(int n) {
		if(n == 1) { //기저조건: 몫이 1이되는 순간

			System.out.println(1);
		}
		else {
			sol(n/2); // 몫을 타고 들어간다. when? 몫==1 일때까지
			System.out.println(n%2);//기저에서부터 올라오면서 출력해야하니까
		}
	}


	public static void main(String[] args) {
		sol(10); // 나머지,나머지,나머지... 몫
	}

}
  • 그럼 8진법은? n/8 과 n%8