[DS] Recursion(재귀)

Recursion(재귀)

자기 자신을 호출하는 함수

• 문제를 더 작은 문제로 나누어 코드를 간결하게 만들어줌
• Breaking Condition이 반드시 있어야 함 (중요)
• Recursion은 호출 될 때 마다 메소드의 복사본이 메모리에 만들어 진다. 그리고 메소드가 종료될 때 메소드의 복사본들은 삭제됨
• Sorting, Search 등의 문제들이 Recursion으로 간단하게 해결 될 수 있음
• 상황에 따라 Iteration이 좋을지 Recursion이 좋을지 잘 판단하여야함

Recursion의 간단한 예시

public class countDown {

	public static void main(String[] args) {
		
		countDown(3); //출력 결과 : 3 2 1 
		
	}
	
	public static void countDown (int integer) {
		System.out.println(integer);
		if (integer > 1) {
			countDown(integer - 1);
		}
	}

}

Recursion과 Iteration 비교

	Recursion	Iteration
기본	함수 자체를 실행	명령을 반복적으로 실행
체재	Breaking Condition만 지정(조건이 추가될 수도 있음)	초기화, 조건, 루프 내 명령문 실행과 제어 변수 업데이트 포함
종료	함수 호출 본문에 조건부가 포함, Recursion를 호출하지 않고 함수를 강제 반환	설정한 조건에 도달 할 때까지 반복 실행
조건	조건에 수렴하지 않을 경우 무한 Recursion 발생	제어 조건이 참이라면 무한 반복 발생
무한 반복	무한 Recursion은 Stack Overflow 발생(메모리 부족)	무한 루프는 CPU 사이클을 반복적으로 사용
스택 메모리	함수가 호출 될 때마다 새 로컬 변수와 매개 변수 집합, 함수 호출 위치를 저장하는데 사용	스택 메모리를 사용하지 않음
속도	느린 실행	빠른 실행
가독성	코드 길이와 변수가 적어 가독성이 높아짐	코드 길이가 길어지고 변수가 많아져 가독성이 떨어짐

Recursion을 사용하는 이유

Recursion은 Iteration과 비교해보았을 때 가독성 외에는 좋은 점이 없어 보임

그럼에도 재귀함수를 사용하는 이유가 있음

 

1. 알고리즘 자체가 재귀적은 표현이 자연스러울 경우

ex) 피보나치 수열 (f(n) = f(n-1) + f(n-2))

이 경우 Iteration을 사용했을 경우 함수가 매우 복잡해지지만, Recursion을 사용할 경우 매우 간단해짐

 

2. 변수 사용을 줄여줄 수 있음

변수 사용이 줄어든다는 것은, 결과적으로 프로그램에 오류가 생길 가능성이 줄어들고, 프로그램이 정상적으로 돌아가는지에 대한 증명이 쉬워진다는 의미

 

3. 가독성이 향상됨

Recursion은 코드량이 줄어들고 사용하는 변수가 줄어들어 가독성이 향상됨

 

# 성능적인 측면만 본다면 Iteration이 Recursion보다 압도적이며 Recursion을 사용하지 않는 것이 맞다. 하지만 Hardware 성능이 좋지 못해 Software 속도를 극한까지 끌어올려야 하는 시대가 아니기에 협업하는 상황을 생각하면 가독성도 고려해 프로그래밍을 해야하기 때문에 프로그램의 목적을 고려하여 Recursion을 사용하는 것이 올바르다.

 

 

 

Reference

https://velog.io/@gillog/Algorithm-%EC%9E%AC%EA%B7%80%EC%99%80-%EB%B0%98%EB%B3%B5%EB%AC%B8

https://medium.com/@sunnkis/%EB%8D%B0%EC%9D%B4%ED%84%B0-%EA%B5%AC%EC%A1%B0-%EC%9E%AC%EA%B7%80-8d96633be4cd