재귀용법(recursive call, 재귀호출)

: 함수 안에서 동일한 함수를 호출하는 형태.

자기 자신을 호출하는 함수.

 

- 재귀 호출의 일반적인 형태 1)

def functino(입력):
if 입력 > 일정값: # 입력이 일정 값보다 크면
   return function(입력-1)
else:
   return 일정값 # 재귀호출종료

#팩토리얼1

def factorial(num):
  if num > 1:    
    return num * factorial(num-1) 
  else:
    return num
 
print(factorial(4))
 

- 재귀 호출의 일반적인 형태 2)

def functino(입력):
    if 입력 > 일정값: # 입력이 일정 값보다 크면
        return function(입력-1)
    else:
        return 일정값 # 재귀호출종료

#팩토리얼2

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

- 재귀함수 디자인을 위한 3가지 절차

1) 함수의 역할을 말로 정확하게 정의한다.

2)기저조건(Base Condition) 에서 함수가 제대로 동작함을 보인다.

3) 함수가 (작은 input에 대하여) 제대로 동작한다고 가정하고 함수를 완성한다.

 

# n^m을 재귀함수를 이용하여 계산하시오

# 디자인

# 1. getPower(n, m) = n^m을 반환하는 함수

# 2. getPower(n, 0) = 1

# 3. getPower(n, m) = getPower(n, m-1) * n

# 구현

def getPower(n, m):
  if m == 0: return 1
  else: return getPower(n, m-1) * n
 
print(getPower(2, 4))

# N to M : n부터 m가지의 합을 구하는 함수

# 디자인

# 1. getSum(n, m) = n부터 m까지의 합을 구하는 함수

# 2. getSum(n, n) = n (기저조건)

# 3. getSum(n, m) = getSum(n, m-1) + m

# 구현

def getSum(n, m):
  if n == m: return n
  return getSum(n, m-1) + m
 
print(getSum(4, 10))

# 각 자릿수의 합 : 십진수 N을 입력받아 각 자리수의 합을 구하시오.

# 디자인

# 1. getSum(n, m) = n부터 m까지의 합을 구하는 함수

# 2. getSum(n, n) = n (기저조건)

# 3. getSum(n, m) = getSum(n, m-1) + m

# 구현

def getDigitSum(x):
  if x >= 0 and x <=9:
    return x
  return getDigitSum(int(x/10)) + (x%10) 
 
print(getDigitSum(1234))

# 이진수 출력하기 : 십진수 N을 입력받아 이진수로 변환하여 출력하시오.

# 디자인

# 1. printBinary(x) = x를 이진수로 바꾼 결과를 출력하는 함수

# 2. printBinary(x)  = 0, printBinary(x)  = 1(기저조건)

# 3. printBinary(x) = printBinary(int(x/2)), print(x%2)

# 구현

def printBinary(x):
  if x == 1:
    print(x)
    return
  elif x == 0:
    print(x)
    return  
  else:    
    printBinary(int(x/2))    
    print(x%2)
 
printBinary(5)

# 팰린드롬(palindrome, 회문) :  문자열의 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장.

# 디자인

# 1. isPalindrome(pStr) = pStr의 첫 번째 문자열과 마지막 문자열을 비교해나간다.

# 2. isPalindrome(pStr) :  len(pStr)  <= 1(기저조건)

# 3. isPalindrome(pStr) =  pStr[0], pStr[-1] 비교, isPalindrome(pStr[1 : -1])

# 구현

def isPalindrome(pStr):
  if len(pStr) <= 1:
    return 'Yes'
  else:
    if pStr[0] == pStr[-1]:
      return isPalindrome(pStr[1 : -1])
    else:
      return 'No'
 
print(isPalindrome('level'))
  

# 리스트합 : 숫자가 들어 있는 리스트가 주어졌을 때, 재귀함수를 이용하여 리스트의 합을 리턴하는 함수를 만드시오

# 디자인

# 1. sumList(data) = data(리스트) 안에 들어있는 값을 0번 째의 값부터 더해 내려간다.

# 2. sumList(data) :  len(data)  <= 1(기저조건)

# 3. sumList(data) =  sumList(data[1:]) + data[0]

# 구현

def sumList(data):  
  if len(data) == 1:
    return data[0]
  return sumList(data[:-1]) + sumList[-1]
  
data_list = [1, 3, 5, 7]
print(sumList(data_list))

# 정수 n에 대해 n이 홀수이면 3*n+1을 하고, n이 짝수이면 n을 2로 나눈다. 이렇게 계속 진행해서 n이 결국 1이 될 때까지 2와 3의 과정을 반복한다. 예를들어 3을 넣으면 아래와 같이 출력된다.

3

10

5

16

8

4

2

1

 

# 디자인

# 1. func(n) = n의 값이 1일 때까지 짝수, 홀수 조건에 해당하는 연산을 해나간다.

# 2. func(n) :  n == 1(기저조건)

# 3. func(n) =  if n%2 == 0: func(3*n+1) else: func(n/2)

# 구현

def func(n):
    print(int(n))
    if n == 1:
        return
    elif n%2 != 0:        
        func(3*n+1)
    else:
        func(int(n/2))
 
func(3)