백준 단계별로 풀어보기!! - 재귀(recursion)

 

https://www.acmicpc.net/step/19

재귀 단계

---

1. 재귀란?

 

간단히 말해서 함수가 자기 자신을 호출하는 용법이다. 언듯보면 for문이나 while문과 동일하다고 볼수 있지만 재귀는 함수내에서 if문을 사용함으로써 그 차이점을 보인다. 

 

def CountNum(num):
    if num == 0:
        print("Count Finished!")
    else:
        print(num)
        CountNum(num - 1)

print(CountNum(10))

 

위에 예시를 보면 함수 내에서 자기 자신을 호출하여 사용하는 것을 볼 수 있다. 위의 코드를 실행하면 결과는 아래와 같다.

 

10
9
8
7
6
5
4
3
2
1
Count Finished!

 

이러한 재귀함수는 점화식을 표현하는데 특화되어있으며 재귀를 사용함으로써 코드를 더 간결히 짤 수 있다.

 

2. 재귀를 이용하여 팩토리얼 구현하기!

https://www.acmicpc.net/problem/10872

10872번: 팩토리얼

 

팩토리얼은 '!' 기호로 수식을 표현하며 그 뜻은 1까지의 숫자를 모두 곱하는 것이다. 예를들어 5!이면 5 x 4 x 3 x 2 x 1 = 120인것이다. 반복문으로도 충분히 표현 가능하지만 여기서는 재귀를 사용하여 구현해보겠다. 

n = int(input())

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

print(factorial(n))

 첫 줄은 팩토리얼을 진행할 숫자를 입력하는 부분이다. 그 후 팩토리얼 함수가 실행이된다. If문에서 input으로 받은 숫자가 1보다 같거나 작으면 1을 반환해주고 아닐 경우 해당 숫자와 다시 팩토리얼 함수로 나온 값을 곱해준다. 즉, 이전 예시처럼 5!을 구현하기 위해 n값으로 5를 주었으면, 들어온 n이 1이 아니므로 5 x factorial(4)를 반환한다. 여기서 factorial(4)는 4 x factorial(3)을 반환한다. 이런식으로 계속 진행하면 5 x 4 x 3 x 2 x 1을 계산하는 함수가 만들어진 것이다.

 

3. 재귀를 이용하여 피보나치 수열 구현하기!

https://www.acmicpc.net/problem/10870

10870번: 피보나치 수 5

 

 피보나치 수열이란, 0과 1로 시작하여 그 다음 수는 앞의 두 수의 합과 같아지는 수열을 뜻한다. 수식으로 쓰면,  Fn = Fn-1 + Fn-2 (n>=2)로 표현할 수 있는 수열이다. 즉, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 방식으로 이어진다. 재귀를 사용해서 구현하면 다음과 같이 구현할 수 있다.

 

n = int(input())

def fivonacci(num):
    if num == 0:
        return num
    if num == 1:
        return num
    return fivonacci(num - 1) + fivonacci(num - 2)

print(fivonacci(n))

 

 fivonacci 함수의 첫 줄을 보면 if문으로 들어온 숫자가 0일 경우 그대로 0을 반환하는 조건이다. 그 다음 if문도 1이 들어올 경우 1을 그대로 반환한다. 이런식으로 조건문을 사용한 이유는 피보나치 수열을 수식화 했을 때 (n>=2)를 표현한 것이라 할 수 있다. 그 후 재귀를 사용하여 fivonacci 함수를 불러와 Fn-1 + Fn-2를 표현한 것이다.

 

4. 재귀를 사용해 별찍기!

https://www.acmicpc.net/problem/2447

2447번: 별 찍기 - 10

 위의 사진처럼 재귀를 사용하여 별을 찍는 게 이번 문제이다.

우선, 기본 별의 형태(3으로 input 값이 들어왔을때)를 아래의 그림 처럼 정의하고 리스트로 만들면

["***", "* *", "***"]이 된다.

크기가 3인 별

 

 특징을 보면 별이 안 찍힌 빈칸이 n = 27인 경우 x축 기준 인덱스가 1, 4, 7, 10, 13, 16, 19, 22, 25이고 이는 y축도 동일하다. 그리고 x, y 축 3,4,5 / 12,13,14 / 21,22,23마다 별이 안 찍혔으며 마지막으로 크게 9, 10 ,11, 12, 13, 14, 15, 16, 17에 별이 안 찍혔다. 즉, 주어진 길이에서 3으로 나눈 나머지의 몫이 1이면  아예 중앙이 뚫리는 형태인것이다. 그리고 그 외는 기본 형태로 채우는 방식으로 코드를 짯다.

 

def stars(star_lst):
    new_star_lst = []
    for i in range(3 * len(star_lst)):
        if i // len(star_lst) == 1:
            new_star_lst.append(star_lst[i % len(star_lst)] + " " * len(star_lst) + star_lst[i % len(star_lst)])
        else:
            new_star_lst.append(star_lst[i % len(star_lst)] * 3)
    return list(new_star_lst)

star = ["***", "* *", '***']
n = int(input())
iter = 0
while n != 3:
    n = int(n / 3)
    iter += 1

for i in range(iter):
    star = stars(star)
for i in star:
    print(i)

 

 stars 함수부터 살펴보면, 들어오는 별 리스트의 길이에 3을 곱한 만큼 반복을 해준다. 그때, 이전에 살펴본 방식대로 3으로 나눈 나머지가 1이면 빈칸을 추가하는 형식으로 반복을 돌려서 코드를 구성하였다.

 

5. 재귀를 사용해서 하노이 탑 이동시키기!

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

 

 

하노이 탑 설명

 

 하노이 탑 옮기기의 특징을 먼저 살펴보자. 원판의 개수 n개가 홀수인 경우 첫 번째 원판을 3번째에 옮겨야하고, n이 짝수인 경우 첫 번째 원판을 2번째에 옮겨야 진행이 가능하다. 이는 n-1번째에도 동일하게 적용된다. 즉, 재귀를 사용하면 된다는 것이다.

 

출력 방식

  

 출력 첫 줄에는 총 옮긴 횟수 k를 출력하고, 나머지는 수행 과정을 출력한다. 이때 수행과정은 A 번째 탑에 가장 위에 있는 원판을 B로 옯긴다는 형식으로 표현한다. 즉 예제 출력 1의 1 3은 1번째 탑에 가장 위에 있는 원판을 3번째 탑으로 옯긴다는 뜻이다. 

 

n = int(input())
movement = []

def hanoi_movement(n, a, b, c):
    if n == 1:
        movement.append((a, c))
    else:
        hanoi_movement(n-1, a, c, b)
        movement.append((a, c))
        hanoi_movement(n-1, b, a, c)

hanoi_movement(n, 1, 2, 3)

print(len(movement))
for move in movement:
    print(move[0], move[1])

 

 움직임을 저장할 리스트를 만들고, 함수 작성을 시작했다. 함수를 살펴보면, n이 1일 때는 움직임이 홀수일때 한 번만 필요하기에 따로 가정법을 빼두었다. a탑에 있는 n(n != 1)번 원판을 c탑으로 옮기기 위해서는 n-1의 원판을 b번으로 옮기고, n번 원판을 c탑으로 옮긴 다음, 다시 n-1번 원판을 c탑으로 옮겨야하는 것을 함수로 적은 것이다.

 

 

 

 

 

 

 

 

https://yeol2.tistory.com/38?category=871927