4강,5강:재귀 알고리즘

유태형·2022년 3월 3일

알고리즘 - Python

목록 보기

3/16

4강 요약

재귀 알고리즘의 원리에 대해 알 수 있었다. 함수에서 종결조건에 다다를 때 까지 함수를 호출하고 합을 도출한다.

내용

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

와 같이 n부터 1까지의 합을 구할때 자기자신을 호출하여 구할 수 있을 것이다.

이때 if n<=1 : return 1;과 같이 조건문 걸어두어 무한히 자기자신을 호출하지 않도록 종결조건을 설정하는 것은 재귀함수를 사용함에 있어 아주 중요하다.

또한 성능적인 면에선 재귀함수가 좋지 못하다. 반복문과 함수호출을 같은 횟수 해야할 때 함수호출의 오버헤드가 훨씬 크기 때문

문제

피보나치 수열을 재귀함수로 구현

def solution(x):
    if x <= 1: //x가 1이면
        return x; //종결 조건
    else: //종결조건이 아니라면
        return solution(x-1) + solution(x-2); //재귀적 호출

5강 요약

재귀적 호출과 반복문을 비교하여 사람이 이해하기 쉬우나 성능이 매우 좋지 않은 재귀적 호출, 재귀호출보단 이해하기 쉬우나 성능차가 뚜렷한 반복문등을 비교

내용

효율성 측면에서 반복문 보다 좋지못한 이유는 여러가지가 있지만 대표적으로 2가지가 있다.
1.함수호출시 발생하는 오버헤드
2.함수호출의 중복

함수호출시 발생하는 오버헤드

알고리즘보단 컴퓨터구조와 관련이 있는데 함수호출시 필요한 동작으론 현재 함수의 위치와 변수들을 저장하고 다음 함수를 호출 + 되돌아 올때 다시 변수 불러오는 동작으로 오버헤드가 발생한다.

함수호출의 중복

이전의 피보나치 수열을 생각해보자

fibo(4) = fibo(3) + fibo(2)

재귀함수로 구하기 위해선 fibo(3)과 fibo(2)도 재귀적으로 함수를 호출 하여야 한다.

fibo(3) = fibo(2) + fibo(1)

fibo(2) = fibo(1) + fibo(0)

fibo(1)과 fibo(0)이 0과 1을 리턴할때까지 함수들이 중복되어 조금만 피보나치수가 증가하더라도 엄처나게 많은 수의 함수들이 중복될 것이다.

다시 fibo(4)를 보면

fibo(4)가 fibo(3)과 fibo(2)를 호출하고 fibo(3)이 또 fibo(2), fibo(1), fibo(0)을 호출하고 fibo(2)가 fibo(1), fibo(0)을 호출함으로써 9개의 함수가 호출됨을 알 수 있다.

피보나치 수열(반복문)

이전에 피보나치 수열을 재귀함수로 짧고 간략하게 구현하였다. 성능의 문제로 피보나치 수열을 재귀함수로 구현하는 것은 큰 수를 구할때 좋지못한 알고리즘임을 위에서 증명해 보았다.
반복문을 통해 피보나치 수열을 고해보자.

def fibo(n):
	if n<=1:
    	return n;
    else:
    	i=2
        t0=0
        t1=1
        while i<=n:
        	t0,t1 = t1, t0+t1
            i+=1
        return t1

0또는 1은 상수이므로 그대로 반환하고 2이상인 수의 피보나치 수열은 전과 전전의 피보나치 수를 기반으로 더하고 치환하는 과정을 수행한다.

문제

반복문으로 구현하였던 이진탐색을 재귀함수로 구현하자.

def solution(L, x, l, u):
    	if l > u: //min값이 max값보다 더 클순 없다
        return -1 //종결 조건
    mid = (l + u) // 2
    if x == L[mid]: //값 일치
        return mid //종결조건
    elif x < L[mid]: //mid보다 작음
        return solution(L,x,l,mid-1) //mid이상의 값은 존재할 수 없다
    else: //mid보다 큼
        return solution(L,x,mid+1,u) //mid이하의 값은 존재할 수 없다.