1. 재귀

• 호출된 함수가 자기 자신을 재호출함

1.1. 팩토리얼 구현하기

• 팩토리얼 : 1부터 n까지의 곱셈(n!)

def factorial(n):
    if n <= 0:
        return 1
    return n * factorial(n-1)

print(factorial(3));    

1.2. 순열 : 재귀 트리

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

ex) {1,2,3} 의 순열 : {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1}

def permutation(arr, start):
    if len(arr) - 1 == start:
        print('start : {}, permutation : {}'.format(start, arr))
        return
    for i in range(start, len(arr)):
        arr[start], arr[i] = arr[i], arr[start]
        print('start:{}, index:{}, arr:{}'.format(start, i, arr))
        permutation(arr, start + 1)
        #arr[start], arr[i] = arr[i], arr[start]
arr = [1,2,3]
permutation(arr, 0)

• 중단 조건 : start가 집합의 마지막 원소에 도달 시 완성된 순열 출력
• i를 통해 집합의 모든 원소 순회
• start와 i 원소 변경