Recursion(재귀)

재귀호출(순환호출)

함수 또는 메소드가 자기 자신을 또 호출하는 형태를 말한다.
파이썬은 무한 호출이 감지되면 중지시키는 RecursionError이 존재한다.
아무리 그렇다고해도 횟수를 정해놓거나, 함수가 종료될수있는 조건을 꼭 넣어두자.

팩토리얼이 좋은 예가 될수 있다.
팩토리얼은 어떠한 숫자를 1이 될 때 까지 1씩줄여가며 곱한 값을 나타낸다.
참고로 0! 은 1 이다.

def factorial(num):
	if num > 1:
    	return num * factorial(num-1)
    else:
    	return num

for num in range(10):
	print(factorial(num))
 >>>
 0
 1
 2
 6
 24
 120
 720
 5040
 40320
 362880

팩토리얼은 n-1번의 팩토리얼 함수를 호출하여 곱셈을 한다. 그러니 시간복잡도는 O(n)

이 재귀 호출은 스택의 전형적인 예이다.

피보나치 역시 좋은 예이다.
참고로 피보나치 수열은 이전 두개의 값을 합해서 그 다음 수를 만들어 나가는 수열이다.

def fibonacci(n):
	if n <= 1:
    	return 0
    elif n ==2:
		return 1
    else:
    	return fibonacci(n-2) + fibonacci(n-1)

하노이 타워

총 3개의 기둥이 있고, 첫번째 기둥에 작은 원판이 위에 있도록 순서대로 쌓여져있다. 첫번째라인의 탑들을 마지막 라인까지 동일한순서를 유지해서 옮기는 문제.
조건
1. 한 번에 하나의 원판만 옮길수 있다.
2. 큰 원판은 작은 원판위에 있을 수 없다.

작은 원판이 큰 원판 위에만 있으면 되니까 당연하지만 그 라인에서 가장 작은 원판만 움직일수가 있다.

# n(입력): 옮기려는 원반의 개수 
# from_pos :  옮길 원반이 현재 있는 출발점 기둥
# to_pos : 원반을 옮길 도착점 기둥
# aux_pos : 옮기는 과정에서 사용할 보조 기둥
def hanoi(n, from_pos, to_pos, aux_pos):
	
    if n == 1: 
    	print(from_post, '->', to_pos)
    	return
    
    hanoi(n-1, from_pos, aux_pos, to_pos)
    print(from_pos, '->', to_pos)
    
    hanoi(n-1, aux_pos, to_pos, from_pos)
print('n=1')
hanoi(1,1,3,2)
print('n=2')
hanoi(2,1,3,2)
    (by book "모두의 알고리즘 with 파이썬")

이런 느낌으로 이동시키면된다.

백준 10872

문제:
0보다 크거나 같은 정수 N이 주어진다. 이때, N! 을 출력하는 프로그램을 작성하시오.

num = int(input())
def factorial(num):
    if num <= 1:
        return 1
    else:
        return num * factorial(num - 1)
    

print(factorial(num))

68ms

백준 10870

문제:
피보나치수열 만드시오

num = int(input())

def fibonacci(num):
    if num <= 0:
        return 0
    elif num <= 1:
        return 1
    else:
        return fibonacci(num-1) + fibonacci(num-2)
print(fibonacci(num))

72ms

num = int(input())

def fibonacci(num):
    if num <= 1:
        return num
    
    else:
        return fibonacci(num-1) + fibonacci(num-2)
print(fibonacci(num))

68ms