직접 구현하기는 물론 작성된 코드를 읽기도 머리아픈 재귀함수.
무엇에 쓰는 함수이고 왜 사용되며, 또 위험성은 어떤 것이 있는지
그리고 함께 배우곤 하는 '꼬리재귀'란 어떤 개념인지 배워봅시다.
또한 많은 컴공 학생들의 두통을 유발하는 🗼하노이의 탑도
최대한 쉽게 이해할 수 있도록 설명해봤어요.
한 번에 알아듣진 못하더라도, 🧐 몇 번 반복해서 듣다 보면
하노이의 탑의 원리를 파악하실 수 있을거에요.
재귀함수(recursive function)가 뭔가요? 00:00~
자기자신을 호출하는 함수 (영상은 JavaScript로 코딩되어 있다)
재귀함수로 작성하면 효율적으로 작성할 수 있는 문제가 있음. (각종 정렬 알고리즘 등)
재귀함수에는 성능 문제가 따를 수 있음.
재귀함수는 호출될 때 마다 스택에 쌓이게 됨 (메모리 부족 발생할 위험 있음)
속도 면에 있어서도 재귀함수는 jump가 잦아서 반복문에 비해 많은 시간을 소모하게 됨
이런 문제를 해결하기 위해 많은 언어들에서 꼬리 재귀 최적화(Tail Call Optimization)라는
기능을 제공한다.
재귀함수를 컴퓨터가 재해석해서 선형 알고리즘으로 만들어 실행하는거죠
그럼 아무리 반복이 많이 일어나도 스택이 넘치는 일이 일어나지 않는다.
만약 재귀함수를 사용하고 싶다면 사용하는 언어가 꼬리 재귀 최적화를 지원하는지 확인하는게 좋다.
재귀함수가 꼬리 재귀가 되려면 return하는 값이 함수 그 자체만 호출하는 형태해야 함
하노이의 탑 설명 03:35~
재귀함수의 일반적인 예제
Engineer, Look Beyond the Code.