[알고리즘] 1. 재귀 알고리즘 (Recursion Algorithm)

안녕하세요!

학교에서 자바와 C, 파이썬을 배우기 시작하면서 알고리즘 공부도 반드시 해야할 것 같아

혼자 공부한 알고리즘도 같이 기록하려고 합니다!

 

알고리즘 중에서도 오늘은 재귀 알고리즘에 대해 정리하려 합니다.

재귀 ( Recursion ) 은 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 말합니다.

그럼 재귀 알고리즘은 어떠한 함수, 메소드가 실행될 때, 또 다시 자기 자신을 불러 연산을 수행하는 것을 말 하겠죠?

 

재귀 호출이라고도 많이 부른다고 합니다.

 

재귀 알고리즘을 사용할때 주의 해야할 것이 반복문을 다룰때 처럼 종료 조건이 있어야 합니다.

종료 조건이 없으면 무한히 자기 자신 호출하게되어 무한 루프에 빠지게 됩니다.

 

재귀 알고리즘의 가장 유명한 예제들 두 가지를 보겠습니다.

 

1. 팩토리얼 계산기

첫번쨰는 팩토리얼 계산기 입니다.

팩토리얼은 N! 을 계산한다 가정할 때 1부터 N까지 모든 정수를 곱하는 것을 말합니다.

 

재귀 알고리즘을 사용한 팩토리얼 계산기

코드를 보시면 

n 을 입력받고 factorial 함수 내에서 n 값이 1이아니면 

n과 factorial(n-1)의 결과 값을 곱하도록 했습니다.

factorial 함수가 반복되면서 n 값은 1이 될 것이고,

그때 마지막으로 1을 곱하면서 n!를 계산한 값이 출력됩니다.

여기서 n == 1 일때 1을 반환하는 부분이 종료 조건을 달아 준 것입니다.

 

반복문

반복문과 함께 비교해 보겠습니다.

반복문은 1에서 n까지 반복하면서 i값을 기존 factorial 값 1 에 곱해주는 식으로 진행됩니다.

n까지 반복한 후 결과 값이 출력됩니다.

 

 

2. 피보나치 수열

두번째는 피보나치 수열입니다.

피보나치 수열은 첫번째, 두번째 수를 제외한 값이 n항의 값이 (n-1번 항 + n-2 번 항) 이 되는 수열입니다.

 

피보나치 수열 점화식

피보나치 수열 with 재귀 알고리즘

정수 n을 입력 받고 n번째 항까지 피보나치 수열을 출력하는 코드입니다.

 

코드를 보시면,

첫번째 항, 두번째 항은 수열의 일반적인 계산과는 다르기 때문에 예외로 빼고 종료 조건을 만들어 주었습니다.

다음 항부터 n번째 항의 값은 fibo(n-2) + fibo(n-1)이라고 정의 해주었습니다.

 

 

여기까지 재귀 알고리즘 설명과 예제였습니다!

수정할 부분있으면 댓글 남겨주세요!

감사합니다!