여러분 안녕하세요. 세이버입니다.
이번 강에서는 재귀함수를 소개해드리겠습니다.
이 강의를 통하여 여러분들은 재귀함수란 무엇이고, 어떻게 사용하는지를 알게 되실 겁니다.
1. 재귀함수란 무엇인가
재귀함수(recursive function)란 함수 내에서 자기 자신을 호출하는 함수입니다.
재귀함수를 알고리즘에 적용시키면 다양한 어려운 문제를 해결할 수 있지만,
입력된 값이 커지면 반복된 호출로 인해 시간과 메모리 공간적 효율이 떨어진다는 단점이 있습니다.
hi 함수는 함수 안에서 hi 함수를 호출하는 재귀함수입니다.
main 함수는 hi 함수를 한번 호출했지만, hi 함수가 계속 본인을 호출하므로 [안녕하세요. POCI입니다.]가 계속해서 출력됩니다.
이 함수의 문제점은 hi 함수가 끝나는 조건이 없어서 계속 hi 함수가 실행되고, 결국 메모리 오버플로우가 발생한다는 것입니다.
위 코드를 실행시키면 [안녕하세요. POCI입니다.]가 계속 출력되고, 메모리 오버플로우가 발생하면 멈추게 되는 걸 보실 겁니다.
그렇기에 재귀함수를 사용하려면 조건문을 이용하여 재귀함수를 끝내는 조건을 추가해야 합니다.
2. return을 이용한 재귀함수의 활용
많은 서적에서 return을 이용한 재귀함수를 다룰 때 제일 많이 사용되는 예제는 펙토리얼입니다.
펙토리얼은 특정한 수보다 적은 수들을 모두 곱하는 수학식입니다.
예를 들어 4!(펙토리얼)은 4*3*2*1이 돼서 24가 되는 거죠.
이를 일반화하면
이렇게 정의할 수 있습니다.
여기서 중요한 것은 n!을 세분화했는데도 (n-1)!이 있다는 것입니다.
즉, 펙토리얼이 펙토리얼 내에서 반복된다는 의미이고, 이를 재귀함수에 적용할 수 있습니다.
fac 함수는 fac 함수 안에서 본인을 호출하는 재귀함수입니다.
그런데 특이한 것은 return 값을 보내는 곳에서 fac 함수를 호출한다는 것입니다.
영상에서와 같이 4를 입력했을 때 동작 과정을 표현하면 다음과 같습니다.
fac(4)는 num이 1보다 크므로 return 값이 4*fac(3)이 됩니다.
fac(3)은 num이 1보다 크므로 return 값이 3*fac(2)이 됩니다.
fac(2)은 num이 1보다 크므로 return 값이 2*fac(1)이 됩니다.
fac(1)은 num이 1이므로 return 값이 1입니다.
다시 거꾸로 올라가서 fac(2)의 return 값이 2*fac(1)이므로 2(2*1)가 됩니다.
fac(3)의 return 값이 3*fac(2)이므로 6(3*2)이 됩니다.
fac(4)의 return 값이 4*fac(3)이므로 24(4*6)가 됩니다.
이런 방식의 재귀함수는 동작 과정이 복잡하기 때문에 여러분들이 직접 다양한 값을 입력했을 때의 동작 과정을 하나씩 필기해가며 숙지하시길 추천드립니다.
이렇게 return 값을 이용하여 재귀함수를 사용하는 방법은 적은 줄로 많은 연산을 하기에 코드의 길이를 줄일 수 있다는 장점이 있습니다.
그러나 입력한 값이 너무 클 경우에는 연산 횟수가 너무 많아져서 결괏값을 출력하는 속도가 느려지게 됩니다.
이번 강의는 여기까지입니다.
오늘도 수고하셨습니다.
정리
- 재귀함수 : 함수 안에서 본인을 호출하는 함수
- 장점 : 복잡한 연산을 쉽게 처리할 수 있다.
- 단점 : 계속적인 함수 호출로 인해 시간적 효율과 메모리 효율이 떨어진다.
- 조건문을 이용하여 재귀함수를 끝내는 조건을 추가해야 한다.
- return 값을 이용한 재귀함수
- 장점 : 적은 코드로 많은 연산을 수행할 수 있다.
- 단점 : 값이 너무 클 경우에는 연산 횟수가 많아지므로 결과를 내는 시간이 오래 걸리게 된다.
강의가 유익하셨거나 마음에 드셨으면 구독과 좋아요, 댓글 부탁드립니다.
궁금하신 점이나 질문은 댓글이나 메일 남겨주세요.
'C언어' 카테고리의 다른 글
| 세이버의 C언어 강의 24강_ 배열이란 무엇인가_Part2(다차원 배열) (0) | 2019.06.12 |
|---|---|
| 세이버의 C언어 강의 23강_ 배열이란 무엇인가 (0) | 2019.06.02 |
| 세이버의 C언어 강의 21강_ 함수란 무엇인가_Part2(함수의 형태와 변수의 종류) (0) | 2019.05.12 |
| 세이버의 C언어 강의 20강_ 함수란 무엇인가 (0) | 2019.05.04 |
| 세이버의 C언어 강의 19강_ 자료형이란 무엇인가 Part4_형변환 (0) | 2019.04.29 |
