재귀

재귀는 간단한게 말해서 다시 돌아간다는 의미이다.
재귀를 잘 표현해주는 이미지는 다음과 같다.

다음과 같이 함수를 까고 까고 또 까는 것이다.

간단한 예제

등차수열

예를 들어서 초항이 1이고 공차가 3인 등차수열의 n항 값을 아는 함수를 만든다고 가정해보자.
우리는 로직을 짤 때 return 을 잘 활용해야 한다.

def seq(n):
	if n == 1:
    	return 1
    else:
    	return seq(n-1) + 3

다음함수가 어떻게 작동하는지 생각해보자.

만약에 내가 n에 10을 넣는다고 생각해보자. 그렇다면 함수가 처음 호출 될 때는 n이 1이 아니기 때문에 return 값으로 seq(9)+3의 값이 나와야 한다.

근데 return 을 해줘야 하는데 안에 함수가 있어서 마트료시카 마냥 또 깐다. seq(9)은 return seq(8) + 3을 하고 계속해서 하다보면 seq(1) + 3이 될 것이다.

이때 seq(1)은 return 1이기 때문에 함수의 호출을 그만하게 된다. 이 값들을 다 정리해서 더해주면 등차수열을 만들 수 있다.

(((1+3)+3)+3 ... ) 같은 방식으로 말이다.

하노이 탑

조금 더 복잡한 예제를 살펴보자.

이 그림을 본 사람들이 많이 있을 것이다. 왼쪽에 있는 탑을 맨 오른쪽에 옮기면 된다.
로직은 간단하다.

1. 왼쪽에 있는 타워의 맨 밑의 원반을 제외하고 중간으로 옮긴다.

2. 맨 맽의 원반을 오른쪽으로 옮긴다.

3. 중간에 있는 탑을 오른쪽으로 옮긴다.
   이게 끝이다.

코드로 구현하면 다음과 같다.

def move(n, src, tmp, dest):
  if n <= 1:
    print("move %d from %c to %c" % (n, src, dest))
    return 

  move(n-1, src, dest, tmp)
  print("move %d from %c to %c" % (n, src, dest))
  move(n-1, tmp, src, dest)

move(3, 'a', 'b', 'c')

결과 값은 다음과 같이 나온다.

move 1 from a to c
move 2 from a to b
move 1 from c to b
move 3 from a to c
move 1 from b to a
move 2 from b to c
move 1 from a to c

한 번 본인 스스로 구현해 보면 좋을 것 같다.