[코드업] 재귀함수 문제집

출처 

https://codeup.kr/problemsetsol.php?psid=21

---

1901 : (재귀 함수) 1부터 n까지 출력하기

1부터 정수 n까지 출력하는 재귀함수를 설계하시오.

def num(a,b):
    if a > b:
        return
    print(a)
    num(a+1,b)
n =int(input())
num(1,n)

1904 : (재귀함수) 두 수 사이의 홀수 출력하기

시작수(a)와 마지막 수(b)가 입력되면 a부터 b까지의 모든 홀수를 출력하시오

def holzzac(start,end):
    if start > end:
        return
    else:
        if start % 2 != 0:
            print(start, end =" ")
    holzzac(start+1,end)
a,b =map(int,input().split())
holzzac(a,b)

import sys
sys.setrecursionlimit(1000000)
 
def my_sum(num):
    global sum_
    if num == 0:
        return
    sum_ += num
    my_sum(num-1)
 
n = int(input())
sum_ = 0
my_sum(n)
print(sum_)

 >> 파이썬 재귀 허용치를 넘는 input 값이 존재해서 파이썬의 최대 재귀 깊이를 늘려줌

import sys

sys.setrecursionlimit(1000000) 

---

1912 : (재귀함수) 팩토리얼 계산

팩토리얼(!)은 다음과 같이 정의된다. n!=n×(n−1)×(n−2)×⋯×2×1 즉, 5×4×3×2×1=120 이다. n이 입력되면 n!의 값을 출력하시오.

def factorial(num):
    if num == 0:
        return 1
    elif num == 1:
        return 1
    return num * factorial(num-1)
n = int(input())
print(factorial(n))

1915 : (재귀함수) 피보나치 수열

피보나치 수열이란 앞의 두 수를 더하여 나오는 수열이다. 첫 번째 수와 두 번째 수는 모두 1이고, 세 번째 수부터는 이전의 두 수를 더하여 나타낸다. 피보나치 수열을 나열해 보면 다음과 같다.   1, 1, 2, 3, 5, 8, 13 …   자연수 N을 입력받아 N번째 피보나치 수를 출력하는 프로그램을 작성하시오.

def fibo(num):
    if num == 0:
        return 0
    elif num <= 2:
        return 1
    return fibo(num-1) + fibo(num-2)
n = int(input())
print(fibo(n))

def fibo(num):
    if num <= 2:
        memo[num] = 1
        return memo[num]
    else:
        if memo[num] != -1:
            return memo[num]
        else:
            memo[num] = fibo(num-1) + fibo(num-2)
            return memo[num]
 
N = int(input())
memo = [-1] * (N+1)
print(fibo(N) % 10009)

>>

• 기존 단순 재귀로는 시간 초과가 뜨는것을 확인함. 기존 재귀 방식의 경우 fibo(1), fibo(2) 호출하면 호출하는 대로 전부 다 계산해야 했기에 중복계산으로 인한 낭비되는 시간이 발생함. 이를 해결하기 위해 메모이제이션 활용해 문제를 풀었음.
• 최종적으로 문제를 풀고 제출해봤는데 분명 정답이 맞다고 생각했지만 오답이 떴음. 10009를 나눈 나머지를 출력하라는 글을 제대로 읽지 못해 발생함. 문제를 잘 읽어야 할 듯
• memo라는 배열에 크기만큼 초기화를 시켜주는 형식으로 풀었음. 처음에는 기본 빈 리스트 [ ] 에 append 하는 형태로 문제를 풀려고 했지만 Index out or range가 뜸. 

---

1920 : (재귀함수) 2진수 변환

어떤 1010진수 nn이 주어지면 22진수로 변환해서 출력하시오. 예) 10    ----->  1010 0    ----->  0 1    ----->  1 2    ----->  10 1024    ----->  10000000000

def bin(num):
    global result
    if num // 2 == 1:
        result.append(num//2)
        result.append(num % 2)
    elif num // 2 == 0:
        result.append(num % 2)
    else:
        bin(num // 2)
        result.append(num % 2)
    return ''.join(map(str,result))
N = int(input())
result= []
print(bin(N))

>> 

2로 계속 나누다 1이나 0으로 나눠 떨어지는 순간부터 나머지를 출력하였음. 

---

1928 : (재귀함수) 우박수 (3n+1) (basic)

콜라츠의 추측, 3n+1 문제, 우박수 문제라고 불리는 이 문제는 다음과 같다. 1, 어떤 자연수 n이 입력되면, 2. n이 홀수이면 3n+1을 하고, 3. n이 짝수이면 n2를 한다. 4. 이 n이 1이 될때까지 2 3과정을 반복한다. 예를 들어 5는 5 → 16 → 8 → 4 → 2 → 1 이 된다. 이 처럼 어떤 자연수 n이 입력되면 위 알고리즘에 의해 1이 되는 과정을 모두 출력하시오.

def collatz(num):
    if num == 1:
        print(int(num))
        return
    else:
        print(int(num))
        if num % 2 == 1:
            collatz(3*num+1)
        else:
            collatz(num * 0.5)
 
N = int(input())
collatz(N)

def collatz(num):
    if num == 1:
        print(int(num))
        return
    else:
        if num % 2 == 1:
            collatz(3*num+1)
        else:
            collatz(num * 0.5)
        print(int(num))
 
N = int(input())
collatz(N)

>>

• 앞의 피보나치와 같이 이 문제 역시 트리 구조 형식처럼 뻗어 내려가면서 중복 계산되는 부분이 많았음.
• 중복계산 낭비를 제거하귀 위해 메모이제이션으로 문제를 풀었음
• 이제까지 푼 문제들은 테스트 케이스와 인풋 값을 정확히 정해줬으나 이 문제는 정확히 명시해주지 않음
• EOF (End of file) 파일의 끝을 의미하며 이 문제에서는 인풋 값의 끝이 왔으나 그것을 예상하지 못하면 EOFError가 발생함. EOFError를 활용하여 try - except를 통해 에러가 발생시 중단하는 방식으로 해결.

---

1953 : (재귀함수) 삼각형 출력하기 1

n이 입력되면 다음과 같은 삼각형을 출력하시오. 예) n 이 5 이면 *  **   ***    ****     *****

def tri(num):
    if num == 1:
        print('*')
        return 
    else:
        tri(num-1)
        print(num* "*")
 
n = int(input())
tri(n)

---

향후 남은 4문제 (파스칼의 삼각형2 / 계단 오르기2 / 우박수 길이 3n+1(large) / 계단 오르기 )

풀이 추가 예정