[알고리즘] 재귀함수 with pyhon

재귀함수

정의 단계에서 자신을 재참조하는 함수

자기자신을 호출하는 패턴을 끝내기 위한 탈출 조건을 만들어야 하는데 이를 기저 조건(Base condition)이라고 한다.

재귀함수 디자인을 위한 3가지 절차 !!! 무조건 !!!

1) 함수의 역할을 말로 정확하게 정의한다.
2) 기저조건(Base condition)에서 함수가 제대로 동작함을 보인다.
3) 함수가 (작은 input에 대하여) 제대로 동작한다고 가정하고 함수를 완성한다.

재귀함수를 이용해서 n중 for문 돌리기 (advanced brute-force)

완전탐색(brute-force)은 for문 돌리면 되는데 입력받은 n값에 따라 n중 for문을 돌려야 하는 경우, 재귀함수를 활용하여 완전탐색한다.

문제

임의의 자연수는 그보다 작은 자연수들의 합으로 표현될 수 있다. 예를 들어 4의 경우,

4
= 3+1
= 2+2
= 2+1+1
= 1+1+1+1

위와 같은 방법으로 표현 될 수 있다. 이 때 , 숫자의 구성이 같으면서 그 순서만이 다른 경우는 같은 경우로 생각하는데, 예를 들어 다음 세 가지 경우는 모두 같은 경우이다.

2 + 1 + 1, 1 + 2 + 1 , 1 + 1 + 2

자연수 n을 입력 받아 이를 n보다 작은 자연수들의 합으로 나타내는 방법을 모두 출력하는 프로그램을 재귀 호출을 사용하여 작성하시오.

입력
첫 줄에 2 이상 20 이하의 자연수 n이 주어진다.

출력
첫째 줄부터 모든 방법을 한 줄에 하나씩 출력한다. 하나의 식 안에는 큰 숫자가 앞으로 오도록 하고, 전체적으로는 앞의 숫자가 큰 식이 먼저 출력되도록 한다. 숫자와 더하기 사이에는 공백이 없다. 그리고 마지막 줄에는 나누어진 자연수의 개수를 출력한다.

풀이

재귀함수 돌려서 완전탐색하고 그 결과를 result 배열에 저장한다.

현재까지 구한 값의 합이 n과 같아지면 탈출한다.

중복체크: 예를들어 n이 4 일 때 1+3과 같은 조합의 경우 3+1조합과 중복된다. 이 경우 3+1조합이 먼저 저장되었기 때문에(문제에서 큰 수에서 작은 수 순서로 나열하라고 제시) result의 index값이 이전 index값보다 큰 경우에 중복처리 시키면 된다.

result=[0]*30 #result에다가 재귀함수 돌린 값들을 저장할것임. 일단 0 30개짜리 빈 배열 만들어놓음. 
n=int(input())
count=0

def getResult(mySum,index): #현재까지 구한 합이 mySum, index번째 숫자를 결정할 차례
  if (mySum==n): #탈출조건 : 현재까지 구한 합이 주어진 n과 같아지면 result와 count를 출력하고 탈출한다.
    print(result[0],end='')
    for i in range(1,index):
      print("+",end='')
      print(result[i],end='')
    print()
    global count
    count+=1
  else: 
    myNumber=0
    if(index==0):
      myNumber=n-1
    else: myNumber = n-mySum
    for i in range(myNumber,0,-1):
      result[index]=i
      if(index>0 and result[index-1]<result[index]): #중복확인
        continue;
      getResult(mySum+i, index+1)  
      
getResult(0,0)      
print(count)