[python] 자료구조 - 재귀 함수

🌏 재귀 함수

• 호출된 함수가 자기 자신을 다시 호출하는 것
• 재귀 함수를 구현하기 위해서는
  1) 언제 어떤 매개변수를 가지고 호출할지 정해야 하고,
  2) 호출을 정지시켜 줄 기저 사례가 필요

1. 팩토리얼 구현

def factorial(n):
    # base case: 재귀 함수가 더 이상 호출되지 않도록 하는 특정 조건
    # 전단받은 매개변수 값이 특정 값에 도달하면 함수가 호출되는 것을 막아줌
    if n<=0: #1 : 0!일 때 1 반환 
        return 1
    return n*factorial(n-1)

if __name__ == "__main__":
    for i in range(1,6):
        print(factorial(i)) #2
    

2. 스택 프레임 (stack frame)

• 함수의 호출시 생기는 공간으로, 함수 실행에 필요한 지역변수들이 할당됨
• 함수 호출시 생성되고 함수 종료시 소멸됨
• 메모리에 생성될 수 있는 크기에 한계가 존재하는데, 이를 초과할 경우 Recursion Depth 에러 발생
• stack overflow: 함수가 어떤 함수를 계속 호출하여 스택 프레임으로 쓰일 메모리 공간이 모자라게 되는 에러

def add_two(a,b):
     c = a + b #4: 지역변수 c가 저장됨
     return c #5: 함수 종료시 스택 프레임 소멸

a = 10 # 1
b = 20 #2
result = add_two(a,b) #3: 함수 호출시 스택 프레임 생성
print(result)

3.순열 (permutation)

• 순서가 있는 집합을 다른 순서로 섞는 것

def permutation(arr,start):
    # base case
    ## start가 집합의 마지막 원소에 도달했을 때 섞을 다른 원소가 없으므로 완성된 순열을 출력함
    if len(arr)-1 == start:
        print(arr)
        return
    # for in range
    ## 인수 1개: 시작 숫자를 지정해 주지 않으면 range 함수는 0부터 시작함.
    ## 인수 2개: 시작 숫자와 끝 숫자를 나타냄. 단, 끝 숫자는 해당 범위에 포함되지 않음.
    for idx in range(start ,len(arr)): # idx로 집합의 모든 원소를 순회하면서 start와 idx의 원소를 바꿈 
        arr[start],arr[idx] = arr[idx],arr[start]
        permutation(arr,start+1) #재귀 함수 호출
        arr[start],arr[idx] = arr[idx],arr[start] # 자신의 스택 프레임으로 돌아온 경우 이전에 바꾸어 놓았던 원소를 원래대로 돌려놓음 
    
if __name__ == "__main__":
        arr=[1,2,3]
        permutation(arr,0)