재귀호출

재귀호출이란?

​

특정 조건을 만족할 때까지 자기 자신을 반복해서 호출하는 것.

​

일반적으로는 가독성이 좋아진다는 장점이 있다.

​

반복문으로 구현하면 복잡해지는 코드가 재귀호출로 구현 시 간략해질 수 있다.

​

스택 메모리에 쌓이고 그 스택메모리가 빌드나 제한된 메모리 이상으로 초과하면 오버플로우가발생한다.

​

스택에 함수가 호출된 주소가 저장되어 있기 때문에 호출 횟수가 많아지면 실행 속도가 느려지는 단점이있다.

​

퀵정렬이나 길찾기 알고리즘에 많이 사용되었고 A스타, XX, XX 등이 있다.

​

꼬리재귀

스택에 쌓지 않는 재귀호출.

​

코드상으로는 재귀함수지만 컴파일러가 반복문으로 최적화하여 반복문처럼 된다.

​

컴파일 옵션에서 꼬리재귀 최적화를 설정할 수 있다.(불가능한 환경도 있다)

​

리턴할 때 시그니처를 동일하게 호출하면 된다.

​

​

주변 분들의 첨언

- C# 대부분 구현체는 꼬리재귀 구현하지 않음

- 꼬리재귀는 절차적 언어에서는 보너스 같은 옵션이지만 함수형 언어에서는 아주 중요한 필수 옵션이다. (함수형 언어는 루프를 재귀로 구현하기 때문)

- 절차적 언어에서는 그냥 루프로 풀어 쓰는게 좋다.

(C#의 경우 객체지향 언어이지만 순수 객체지향 언어라고 할 수 없음. '멀티 패러다임 언어' 라고 함. 따라서 절차지향, 객체지향 두 카테고리에 모두 속함)

- '순수 객체지향 언어'는, 아예 OOP적인 구조를 사용하지 않으면 코딩이 아예 안 되도록 문법으로 강제한 언어들이 대부분인데 C#도 크게는 그 카테고리에 속하지만 그렇지 않은 구멍이 많으므로 순수하게 객체지향 언어는 아니다.

​

​

참고자료

Bouncing on your tail

 

다람쥐와 포동포동이

RememberCook 9월 28일 정식 출시!