[개미의 걸음 Python 24차시] 재귀함수와 ★메모화★ with 팩토리얼, 피보나치 수열

재귀 함수[Recursion Function]

함수 내부에서 자기 자신을 호출하는 함수

• 상황에 따라 같은 것을 기하급수적으로 많이 반복한다는 문제가 있어 잘 사용하지 않는 편.
• 한 번 계산한 값을 딕셔너리에 저장해 놓은 후, 이후에 다시 계산하지 않고 저장된 값을 활용하는 메모화[Memoization]을 통해 같은 값을 반복해서 구하는 문제를 해결
     → 메모화를 사용하면 속도가 빨라져 실행 후 곧바로 결과를 출력 가능
• 조기리턴[early returns]을 활용하면 더 간단하게 코드 작성 가능

   재귀함수의 활용 ①. 팩토리얼[Factorial]

n!=n * (n-1) * (n-2) *  ....... * 1

 

   재귀함수의 활용 ②. 피보나치 수열

n≤2일때, f(n)=1
n>2일때, f(n)=f(n-2)+f(n-1)

• 한 번 구했던 값이라도 처음부터 다시 계산해야 하므로 입력하는 숫자가 커질수록 시간은 오래 걸림
• 따라서 딕셔너리를 사용해 한번 계산한 값을 저장함으로써 코드의 속도를 빠르게 해줌[메모화]

       ★ 메모화를 사용한 재귀함수

• 메모화를 사용하면 실행하자마자 곧바로 결과를 출력할 정도로 속도가 빨라짐!!!