[Algorithm] 재귀함수(Recursive Function) 개념 정리

재귀란

• 컴퓨터 과학에서 재귀란 자신을 정의할 때 자기 자신을 재참조하는 방법을 의미한다.

 

재귀함수란

• 함수가 직접 또는 간접적으로 자신을 호출하는 프로세스.
• 재귀 알고리즘을 이용하면 복잡한 문제들도 간단하게 해결 할 수 있다.
• 호출이 깊어지면 성능의 저하가 있을 수 있다.
• 종료지점을 구현하지 않으면 스택 오버플로우가 발생할 수 있다.

 

재귀함수 장단점

장점

• 변수의 사용을 줄여준다.
• 코드의 가독성을 높일 수 있다.

단점

• 시간복잡도가 반복문에 비해 계산이 어렵다.
• 반복문보다 메모리 사용량이 많고 수행 시간이 더 길어질 수 있다.
• 함수 호출을 많이 하기에 StackOverFlow의 가능성이 잇다.
• 종결조건을 정하지 않으면 무한 반복이 일어난다.

 

재귀함수 사용의 예

• 1부터 n까지의 합
• ! 팩토리얼
• 최대공약수 문제
• 피보나치 수열 구하기
• 문자열의 길이를 구하는 등의 문제
• 2진수 변환하기 문제
• 배열 총합 문제