#재귀함수

def recursion_function():
    print("hey")
    recursion_function()
recursion_function()

#재귀호출 (탈출구)

def recursion_function(i):
    print("hey")
    if i < 10:
        recursion_function(i + 1)
recursion_function(0)

**탈출구를 만드는 방법이 중요

#재귀호출로 팩토리얼 구하기

def factorial(n):
      if n == 1:
           return 1
      return n * factorial(n-1)
print(factorial(5))

피보나치 수열을 이용한 재귀함수 개념

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + fib(3)
((fib(2) + fib(1)) + fib(2) + fib(3)
(((fib(1) + fib(0)) + fib(1)) + fib(2)) + fib(3)
1단계: ((1 + 0) + 1) + fib(2) + fib(3)
2단계: (2 + (fib(1) + fib(0))) + fib(3)
3단계: (2 + (1 + 0)) + fib(3)
4단계: 3 + 2(*위에fib(3)을 찾으세요)
5단계: 5

#재귀함수의 전형적인 문제: n의 숫자만큼 2의 n승 만큼 호출하기 때문에 시간이 상당히 걸
#counter라는 변수를 만들어 계산이 몇번 이루어지는지 알아보기

출력값: 120

#재귀함수 (마지막 발표)
정의: 함수안에 함수가 함수를 부르고 그 함수가 또 함수를 부르기를 반복하기 때문에 결과는 무한히
반복. 그러므로 반드시 반복을 피하기 위한 "장치" 필수!

*factorial(n) 기본 틀
def factorial(n):
    output = 1
    for i in range(1, n+1):
        output *= i
    return output

print("1!:", factorial(1))
print("2!:", factorial(2))
print("3!:", factorial(3))

재귀함수의 문제점: 현재 같은 값을 구하는 연산을 반복하고 있기 때문에 연산 시간이 길어지는
문제점이 생김. 따라서 같은 값을 한 번만 계산하도록 코드를 수정하자.

#재귀함수의 문제점을 해결해주는 **메모화(memoization)

메모 = { 1: 1, 2:1 }
def fib(n):
    if n in 메모:
        return 메모[n]
    else:
        output = fib(n-1) + fib(n-2) #아웃풋이라는 변수에 저장
        메모[n] = output          # 한번 저장 했던 값이니까
        return output
print(fib(100))

#이는 한번 계산 했던 것은 다시 계산하지 않고, 메모 했던 것을 확인하기 때문이

**재귀함수는 보편적으로 while이나 for 같은 반복문으로 대체가 가능하다, 하지만 배열 안에 배열이 겹겹히 있는 경우: lst = [3, [1, 4, [2], 3], 9, 7] << 라면 모든 배열을 일일히 for나 while을 사용해 선언해주어야한다. 하지만 재귀함수를 이용하면 한번에 가능하다.