자료구조와 알고리즘4

재귀 알고리즘 (Recursive Algorithms) 기초

4. 재귀 알고리즘 기초 (Recursive Algorithms)

재귀 함수
하나의 함수에서 자신을 다시 호출하여 작업을 수행하는것 생각보다 많은 종류의 문제가 재귀적으로 해결가능

재귀 함수의 간단한 예 - 자연수의 합 구하기
1부터 n까지 모든 자연수의 합을 구하시오

def sum(n):
	print(n)
    if n <= 1:
    	return n
    else:
    	return n+sum(n-1)

• 재귀 함수에서는 종결 조건이 중요하다
  (종결조건 설정오류시 무한루프에 빠질 수 있다)

재귀 알고리즘의 효율

	재귀방식	반복방식
시간 복잡도	O(n)	O(n)
효율성	함수 호출 후 연산	바로연산
	(효율 떨어짐)	(효율 상대적 좋음)

4강 실습

피보나치 순열을 출력하는 함수를 만드시오

반복적인 버전

def solution(x):
    if x == 0:
        return 0
    if x == 1:
        return 1
    else :
        past = 0; now = 1; answer = 0
        for i in range(1,x):
            answer = (now+past); past = now; now = answer
        return answer

재귀적인 버전

def solution(x):
    if x == 0:
        return 0
    elif x == 1:
        return 1
    else :
        return solution(x-1) + solution(x-2)