재귀 함수 연습 (파이썬)

https://1ncomparable.tistory.com/208

230213 - 재귀

 

재귀 함수 정리

• 재귀 함수는 자기 자신을 호출하는 함수이다. 반복적인 작업을 해야할때 유용하게 사용할 수 있다. 

 

sum(n) : 1부터 num까지의 합을 리턴해주는 함수

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

• 코드 풀이
• sum(5)가 호출
• sum(5) 내부에서 5 + sum(4)가 반환. sum(4) 실행
• sum(4) 내부에서 4 + sum(3)이 반환. sum(3) 실행
• sum(3) 내부에서 3 + sum(2)가 반환. sum(2) 실행
• sum(2) 내부에서 2 + sum(1)이 반환. sum(1) 실행
• sum(1) 은 조건문에 걸려서 n을 리턴. n은 1. 함수 호출이 끝났으니 결과가 반환되기 시작함.
• sum(2)의 리턴값은 2 + 1(= sum(1))이 됨.
• sum(3)의 리턴값은 3 + 2 + 1.
• sum(4)의 리턴값은 4 + 3 + 2 + 1.
• sum(5)의 리턴값은 5 + 4 + 3 + 2 + 1.
• 결과로 15가 리턴이 된다.

 

fac(n) : n!의 값을 리턴해주는 함수 

def fac(n):
    if n == 1:
   	 	return 1
    return n * fac(n-1)

• sum과 동일

 

fibo(n) : n번째 피보나치 수열을 리턴해주는 함수 

def fibo(n):
    if n == 1 : return 1
    if n == 2 : return 2
    return fibo(n-1) + fibo(n-2)

• 피보나치 수열 - 1, 2, 3, 5, 8... => n번째 값을 구하기 위해서는 n-1과 n-2를 알아야 함. n의 값이 (n-1) + (n-2)이기 때문!
• 하지만 이 방법은 효율성이 좋지 못하다. 이미 계산된 값도 의미 없이 다시 계산을 반복하기 때문이다.

 

memo = {0:0, 1:1, 2:2} # 결과값을 저장할 딕셔너리
def fibo2(n):
	if n in memo:
    	return memo[n]
	memo[n] = fibo2(n-1) + fibo2(n-2)
    return memo[n]

print(fibo2(5))

• 결과값을 저장해줄 딕셔너리 memo를 선언하고 활용한 함수
• memo의 초기값을 지정해줌. 
• 함수가 호출되면 먼저 memo에 해당하는 값이 있는지 확인함
• 값이 있다면 그 값을 반환함. = 이미 계산한 값을 재사용
• 값이 없다면 fibo2(n-1) + fibo2(n-2)의 값을 재귀적으로 계산
• 계산한 값을 memo에 저장한 후 반환 

 

• 풀이 과정
• fibo(2) 호출. 5가 memo에 없음
• memo[5] = fibo2(4) + fibo2(3) 연산. 
• fibo2(4) => memo에 없음. memo[4] = fibo2(3) + fibo2(2) 연산
• fibo2(3) => memo에 없음. memo[3] = fibo2(2) + fibo2(1) 연산
• fibo2(2) => memo에 있음. 2 리턴
• fibo2(1) => memo에 있음 1 리턴. memo[3]에 2+1 = 3 저장됨
• memo[4]에 fibo2(3) (=memo[3]) + fibo2(2) (=memo[2]) = 5 저장됨
• memo[5]에 fibo(4)(= memo[4] = 5) + fibo2(3) (=memo[3] = 3) = 8 저장됨
• return memo[5] => memo[5]에 저장된 8이 리턴됨 
• 결과적으로 print 되는 것은 8

 

 

----------

재귀... 오랜만에 하니까 좀 까먹기도 했고 헷갈리기도 해서 중간에 열심히 손코딩 하면서 정리함 

안까먹게 열심히 쓰고 잘해보자