재귀함수란?

재귀함수란 어떤 함수 func(n)이 있다고 할 때, 이 함수 내부에서 자기 자신을 다시 호출하는 함수를 의미한다.


1) 재귀함수의 특징

재귀 함수는

  1. 자기 자신을 호출하는 부분
  2. 일정 조건을 만족하면 호출을 정지하고 어떤 값을 return하는 부분

이 두 분으로 나뉘어진다.

그리고 함수 호출은 메모리의 스택 영역에 쌓이게 되는데, 스택은 후입선출(LIFO)방식으로 데이터를 저장하는 자료구조임을 우리는 알고 있다. 따라서, 아래 함수를 실행했을 때 스택 영역에 쌓이는 함수는 다음과 같다.

def sol(n):

	if n == 5:
		return

	else:
		return sol(n+1)

sol(0)

Untitled


2) 재귀함수 짜는 법

1.  자신을 호출하는 것을 정지시키는 조건을 만들어야 한다.

  1. 한 동작마다 해야하는 것들을 정의해서, 함수 내부에 써넣는다.
  2. 다음 함수를 호출할 때, 파라미터로 어떤 것들을 넘겨줘야 할 지 정해야 한다.


재귀함수의 예시

1. 팩토리얼

def factorial(n):
    if n == 1:      # n이 1일 때
        return 1    # 1을 반환하고 재귀호출을 끝냄
    return n * factorial(n - 1)    # n과 (factorial 함수에 n-1을 넣어서 반환된 값)을 곱함


2. 거듭제곱

def solution2(x,n):
	if n == 0:
		return x
	else:
		return x * solution2(x,n-1)


3. 피보나치수열

  • 피보나치 수 : 첫번째와 두번째 값이 1이고 다음부터는 그 전의 수와 그 전전의 수를 더하는 방식

첫 번째 값이 0으로 시작하는 경우도 있으며 다음과 같은 형태의 수열이다.

                                                       (0), 1, 1, 2, 3, 5, 8, 13, ...

def fib(n):

	if n == 0:
		return 0

	elif n == 1 or n == 2:
		return 1

	else:
		return fib(n - 1) + fib(n - 2)


4. 하노이의 탑

하노이의 탑 문제는 재귀 호출을 이용하여 풀 수 있는 가장 유명한 예제 중의 하나이다. 그렇기 때문에 프로그래밍 수업에서 재귀 알고리즘 예제로 많이 사용한다.

# 입력 : 옮기려는 원반의 개수 n
# 옮길 원반이 현재 있는 출발점 기둥 from_pos
# 원반을 옮길 도착점 기둥 to_pos
# 옮기는 과정에서 사용할 보조 기둥 aux_pos
# 출력 : 원반을 옮기는 순서

def hanoi(n, from_pos, to_pos, aux_pos):

	if n == 1 :         # 원반 한 개를 옮기는 문제면 그냥 옮기면 됨
		print(from_pos, '->', to_pos)
		return

	hanoi(n - 1, from_pos, aux_pos, to_pos)   	# 원반 n-1개를 aux_pos로 이동(to_pos를 보조 기둥으로)

	print(from_pos, '->', to_pos)     # 가장 큰 원반을 목적지로 이동
	hanoi(n - 1, aux_pos, to_pos, from_pos)    	# aux_pos에 있는 원반 n-1개를 목적지로 이동 (from_pos를 보조 기둥으로)

print('n = 1')
hanoi(1, 1, 3, 2) # 원반 한 개를 1번 기둥에서 3번 기둥으로 이동

n = 1

1 -> 3

print('n = 2')
hanoi(2, 1, 3, 2) # 원반 한 개를 1번 기둥에서 3번 기둥으로 이동

n = 2

1 -> 2

1 -> 3

1 -> 3


이 문제의 핵심은 3가지 원기둥을 1,2,3 이라고 정하는데 이 뜻은 시작,보조,목표 기둥 3가지이다.

이 기둥 번호들을 통해서 원반이 어떻게 이동되는지를 기둥 번호로 나타내는 것!