[데이터 구조와 알고리즘] 순환(Recursion)

순환 (Recursion, 재귀함수 )

자기 자신을 호출하는 함수, 메서드

 

 

1. 무한루프에 빠지지 않도록 주의( 아래 코드는 무한 루프에 빠지게 됨 )

package data;

public class algo {

	public static void main(String[] args) {
		func();
	}
	
	public static void func(int k) {
		System.out.println("Hello !");
		func();
	}
}

 

아래 코드처럼 Base case와 recursive case의 조건을 만족해야 무한 루프에서 빠져나올 수 있다.

package data;

public class algo {

	public static void main(String[] args) {
		int n = 4;
		func(n);
	}
	
	public static void func(int k) {
		if(k <= 0)		//Base case : 순환에 빠지지 않는 경우가 존재해야 함
			return;
		else {
			System.out.println("Hello !");
			func(k-1);		//Recursive case: recursive을 반복하다보면 base case로 수렴해야 함
		}
	}
}

 

---

1~n 까지의 합

package data;

public class algo {

	public static void main(String[] args) {
		int result = func(4);
		System.out.println(result);
	}
	
	public static int func(int n) {
		if(n == 0)	
			return 0;
		else 
			return n + func(n-1);
	}
}

 

팩토리얼 n!

package data;

public class algo {

	public static void main(String[] args) {
		int result = factorial(4);
		System.out.println(result);
	}
	
	public static int factorial(int n) {
		if(n == 0)	
			return 1;
		else 
			return n * factorial(n-1);
	}
}

 

x의 n제곱

package data;

public class algo {

	public static void main(String[] args) {
		double result = pow(4.0, 4);
		System.out.println(result);
	}
	
	public static double pow(double x, int n) {
		if(n == 0)	
			return 1;
		else 
			return x * pow(x, n-1);
	}
}

 

피보나치 수열

package data;

public class algo {

	public static void main(String[] args) {
		double result = fibonacci(6);
		System.out.println(result);
	}
	
	public static double fibonacci(int n) {
		if(n < 2)	
			return n;
		else 
			return fibonacci(n-1) + fibonacci(n-2);
	}
}

 

최대 공약수

package data;

public class algo {

	public static void main(String[] args) {
		double result = gcd(24, 36);
		System.out.println(result);
	}
	
	public static double gcd(int m, int n) {
		if(m < n) {
			int temp = m;
			m = n;
			n = temp;
		}
		if(m%n == 0)	
			return n;
		else 
			return gcd(n, m%n);
	}
}

 

---

문자열의 길이 계산

*scanner

*substring

package data;

import java.util.*;

public class algo {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String result = scan.nextLine();
		System.out.println(len(result));
	}
	
	public static int len(String str) {
		if(str.equals(""))
			return 0;
		else
			return 1 + len(str.substring(1));
	}
}