[코드업] 문제집 : 재귀함수 1901~ 1930

codeup.kr/problemsetsol.php?psid=21

문제집 / 재귀함수

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

n = int(input())

def recursive(num):
    if num > 1:
        recursive(num-1)
    print(num)    
recursive(n)
## 출력
# 1
# 2
# 3
# 4
# 5
# 6
# 7
# 8
# 9
# 10

 

1902 : (재귀 함수) 1부터 n까지 역순으로 출력하기

n = int(input())

def recursive(num):
    print(num)
    if num > 1:
        recursive(num-1)
        
recursive(n)

 

 

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

a, b = map(int, input().split())

def recursive(A, B):
    if A > B:
        return
    if A % 2 == 1:
        print(A, end=' ')
    recursive(A+1, B)
        
recursive(a, b)
# recursive(2, 7) # 3 5 7

 

1905 : (재귀함수) 1부터 n까지 합 구하기

import sys
sys.setrecursionlimit(1000000) 

n = int(input())

def recursive(num):
    if num <= 1:
        return num
    else:
        return num + recursive(num-1)
        
print(recursive(n))

 

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

n = int(input())

def Factorial(n):
  if n == 0:
    return 0
  elif n == 1:
    return 1
  else:
    return n * Factorial(n-1)

print(Factorial(n))

 

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

# 첫 번째 수와 두 번째 수는 모두 1이고, 
# 세 번째 수부터는 이전의 두 수를 더하여 나타낸다.

n = int(input())

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

 

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

# 첫 번째 수와 두 번째 수는 모두 1이고, 
# 세 번째 수부터는 이전의 두 수를 더하여 나타낸다.
# N 이 커질 수 있으므로 출력값에 10,009를 나눈 나머지를 출력한다.

def Fibonacci(n):
  if n == 0:
    mem[n] = 0
    return mem[n]
  elif n <= 2:
      mem[n] = 1
      return mem[n]
  else:
    if mem[n] != -1: # 그 전에 기록 됨
      return mem[n]
    else:
      mem[n] = Fibonacci(n-2) + Fibonacci(n-1)
      return mem[n]
    
n = int(input())
mem = [-1] * (n+1)
print(Fibonacci(n)%10009)

 

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

# 7 -> 111, 8 -> 1000

def toBinary(n):
  if n<= 1:
    print(n, end='')
    return 
  else:
    toBinary(n//2)
    print(n % 2, end='')
  
n = int(input())  
toBinary(n)

 

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

# 1, 어떤 자연수 n이 입력되면,
# 2. n이 홀수이면 3n+1을 하고,
# 3. n이 짝수이면 n/2를 한다.
# 4. 이 n이 1이 될때까지 2 3과정을 반복한다.

def recursive(n):
  print(n)
  if n == 1:
    return
  else:
    if n % 2 == 1:
      # print(3*n + 1)
      recursive(3*n + 1)
    else:
      # print(n // 2)
      recursive(n // 2)
 

n = int(input())  
recursive(n)
# 5
# 16
# 8
# 4
# 2
# 1

 

1929 : (재귀함수) 우박수 (3n+1) (reverse)

# 1, 어떤 자연수 n이 입력되면,
# 2. n이 홀수이면 3n+1을 하고,
# 3. n이 짝수이면 n/2를 한다.
# 4. 이 n이 1이 될때까지 2 3과정을 반복한다.

def recursive(n):
  if n == 1:
    print(n)
    return
  else:
    if n % 2 == 1:
      recursive(3*n + 1)
    else:
      recursive(n // 2)
  print(n)
 

n = int(input())  
recursive(n)
# 1
# 2
# 4
# 8
# 16
# 5

 

1930 : SuperSum

# SuperSum(0,n) = n
# SuperSum(k,n) = SuperSum(k−1,1) + SuperSum(k−1,2) + ... + SuperSum(k−1,n)
# 메모제이션 x, 입력 반복 x
def SuperSum(k, n):
  print(k, n)
  if k == 0:
    return n
    
  else:
    res = 0
    for i in range(1, n+1):
      res += SuperSum(k-1, i)     
    return res

k , n = 2, 3
print(SuperSum(k, n))
# 2 3
# 1 1
# 0 1
# 1 2
# 0 1
# 0 2
# 1 3
# 0 1
# 0 2
# 0 3
# 10

# SuperSum(0,n) = n
# SuperSum(k,n) = SuperSum(k−1,1) + SuperSum(k−1,2) + ... + SuperSum(k−1,n)
# 메모제이션 x, 입력 반복 x
def SuperSum(k, n):
  # print(k, n)
  if k == 0:
    return n
    
  else:
    res = 0
    for i in range(1, n+1):
      res += SuperSum(k-1, i)     
    return res

k , n = 2, 3
mem = [[0] * (k+1)] * (n+1)

mem[1][2] = 1
print(mem)

print(SuperSum(k, n))