on
재귀함수 - Recursive Functions
재귀함수 - Recursive Functions
재귀함수란 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것.
의외로 많은 것들을 이 재귀함수로 해결할 수 있다고 하니 한번 알아보자.
1. 이진트리(binary trees)
12를 기준으로 왼쪽에는 12보다 작은 수 9가 있고, 오른쪽엔 12보다 큰 17이 있다.
한단계 더 내려가서 9를 기준으로 왼쪽에는 9보다 작은 5가 있고, 오른쪽엔 9보다 큰 10이 위치하고 있다.
오른쪽도 마찬가지로 17을 기준으로 왼쪽에는 17보다 작으 수 15가 있고, 오른쪽엔 23이 있다.
이렇게 재귀적인 정의를 만족시키는 트리를 가지고 있을 때
10을 찾으려 할 때 재귀적인 방법으로 찾을 수 있다.
첫번째 루트노드 12부터 시작하면 10은 12보다 작기 때문에 왼쪽으로 이동한다.
또한 9에서 우리가 찾으려 하는 노드는 9보다 크기 때문에 오른쪽으로 이동하여 10을 찾게 된다.
이진탐색과 매우 비슷한 구조를 이렇게 재귀적인 방법으로 트리라는 자료구조를 정의해서 이용할 수 있다.
이처럼 컴퓨터 싸이언스에서 주어지는 많은 문제들이 재귀적으로 풀어질 수 있기 때문에 좀 더 살펴볼 필요가 있다.
좀 더 간단한 예로 자연수의 합을 구하는 문제도 재귀호출을 이용하여 풀 수 있다.
이 문제를 수식으로 적어보면 시그마 기호를 이용해서 k가 1부터 n까지 변화할 때 각 k의 값들을 하나하나 다 더해나가면 1부터 n까지의 합인 s를 구할 수 있다.
식을 좀 더 펼쳐서 적어보면
S는 k를 1부터 n-1까지 변화시키면서 자연수의 합에 n을 더하면 된다.
이 식을 파이썬 코드로 풀어내면 sum이라는 함수를 정의하고 n 더하기 sum(n-1)를 준 값 즉 1부터 자연수의 합을 구할 수 있을 것 같다.
과연 잘 적용이 될 수 있을지 확인해 보자
def sum(n): return n + sum(n-1) number = int(input("Number: ")) print(sum(number))
실행을 시켜보면
RuntimeError: Maximum recursion depth exceeded 에러가 발생한다.
자 그러면 이 함수가 호출되면서 매번 호출된 인자 값을 출력해보도록 하자
def sum(n): print(n) return n + sum(n-1) number = int(input("Number: ")) print(sum(number))
넘어오는 인자 값을 확인해 보면
끝 없이 증가하는 것을 확인할 수 있다.
예상된 결과이다.
def sum(n): print(n) #파이썬에서 n이 주어지면 return n + sum(n-1) #재귀호출 시 빠져나오지 못하고 n 끝없이 -가 된다 number = int(input("Number: ")) print(sum(number))
이를 수정하려면
def sum(n): if n <= 1: return n else: return n + sum(n-1) number = int(input("Number: ")) print(sum(number))
이렇게 되야할 것이다.
이 처럼 재귀 호출에는 종결 조건이 아주 중요하다.
그럼 재귀 알고리즘의 효율을 확인해 보자
언제나 재귀호출과 함께 비교되는 반복문과 함께 확인해 보자
n이 커지면 왼쪽의 재귀알고리즘의 소요시간은 얼마나 커질까?
n이 커지면 n에 다라서 함수를 호출해야함에 따라 n에 비례하는 복잡도를 가진다.
반면 오른쪽의 반복문일 경우 마찬가지로 n이 커질수록 반복횟수가 증가하기 때문에 n에 비례하는 복잡도를 가진다.
하지만 복잡도가 아닌 효율성으로 보자면 왼쪽의 재귀호출은 n이 증가하면 n의 크기에 따라 함수를 호출하고 리턴해야하는 부가적인 요소가 있기에 효율성에서는 반복문에 비해 떨어지게 된다.
재귀알고리즘은 우리의 사고를 표현하기에 유리하지만 효율적인 면에서는 떨어진다.
극단적인 예를 들어
1부터 자연수 n까지의 수를 더한다고 하면 위와 같이 구할수도 있다.
이 알고리즘은 상수시간에 실행되어 보다 더 효율적이다.
재귀 알고리즘의 추가 예제
재귀 알고리즘으로 위와 같은 팩토리얼도 구현할 수 있다.
마지막으로 연습문제...(다음 포스팅)
피보나치 수열을 재귀함수, 반복문으로 구현하기이다.
개인확인용 게시글이라 너무 두서 없이 막 적었지만 적었다는데 의의를 두자 ...
from http://la-douleur-passe-la-beaute-reste.tistory.com/20 by ccl(A) rewrite - 2021-11-10 21:00:42