[파이썬] 재귀함수를 이해해보자 feat 10829, 1769, 10872, 2447

그래프를 들어가려하니 재귀는 필수인듯하여 재귀문제를 조금 풀어보고 들어가보려 한다

 

먼저 한 것은 solved에서 재귀 태그를 가진 문제를 난이도별로 정렬, 하나씩 풀어보았다

 

10829 - 이진수 변환

 

 

이 문제는 보자마자 감이왔다

 

a를 2로 나누고 계속 함수에 쌓고 0이면 print로 쌓인 것들을 하나씩 꺼내 출력한다 

 

사실 이 문제는 재귀보다는 그냥 단 한줄로 문제를 풀어버릴 수가 있다

 

print(str(bin(int(input()))[2:]))

근데 우리의 목적은 재귀를 사용하여 문제를 푸는 것이니 재귀를 이용해 코드를 작성해보자

def bin(a):     if a >1:         bin(a//2)     return print(a%2,end="") bin(int(input()))

내용은 간단하다

 

bin(a)를 만들고

 

a가 0이상이면 아직 1이나 0으로 변환할수있다는 뜻이기때문에

a>0

그게 아니다면 계산은 끝났으므로 배열에 쌓인 값들을 pop으로 빼듯

 

뒤에서부터 a//2값을 빼온다

 

그림으로하면 이렇다

 

 

자, 이진수를 풀었으니 이번에는 배수로 가보자

 

1769번 3의배수 문제이다

 

이것도 느낌은 왔다

 

들어온 숫자를 한자리씩 다 더해서 반환해주고 반환할때마다 카운터에 +1해준다

 

반환값이1의 자리일경우 3으로 나눈나머지를 토대로 출력을 시킨다

 

코드는 ..

def bae(a, cnt):     if int(a) < 10:         if int(a)%3 ==0:             return print(cnt), print("YES")                     else:             return print(cnt), print("NO")     cnt+=1     bae(str(sum(map(int,[*a]))), cnt)     bae(input(), 0)

근데 막상 적고보니 재귀라고 하기에는 그냥.... 그렇다

 

그냥 이게 재귀로 풀 가치가 있는가에대한 의문도 들긴한다

 

코드는 단순하다 

bae라는 함수 선언

 

입력값과 0을cnt로 넣는다

 

bae함수에서는

앞서 말한대로

 

*a로 한자리씩 값을 풀어

각각의 값을 map으로 인트값을 만들어준뒤

sum으로 다 더하고

다시str로 씌워준다

 

이렇게 만든값과 cnt를 다시 bae로 호출한다

 

 

그럼 간단하게 값이 나온다 

 

 

이번에는 팩토리얼을 알아보자

 

n!값을 구하는 문제이다

 

아마 이게 제일 대표적인 문제가 아닐까한다 

 

사실 이진법으로 시작해서 차츰차츰 단계를 높여오면 더 좋을듯한데 ..

 

일단 이것도 금방 풀 수 있을 것같다

 

n이 들어오면 

 

n*(n-1)을 계속 호출해주는 코드를 짜면 금방 나올 것 같다

 

def fac(a):     if a == 0:         return 1     else:         return a*fac(a-1) print(fac(int(input())))

오히려 3의배수보다 더 빨린 풀린느낌이다

 

n은 곱해야하니 그냥 놔두고 fac(a-1)

 

이게 다시 돌아가면 fac(a-1)*fac(a-1)

 

또 돌아가면

 

fac((fac(a-1)-1)....

 

이렇게 반복하다가

 

1이 들어가는 순간

 

 

5부터 괄호안 4..3..2..1 차례대로 곱해지고 답이 나온다

 

이번에는 .. 대망의 별찍기로 넘어가보자 ..

 

이해를 위해 출력도 같이 적었다(n=27)

 

 

자, 이게 어떻게 돌아가는가를 알아보자 

 

그냥 문제를 슥 읽고 예제를 보면

 

저런식으로의 패턴을 찾을 수가 있다

 

3일때

***

* *

***

9일때

*********
* ** ** *
*********
***   ***
* *   * *
***   ***
*********
* ** ** *
*********

 

결국 3짜리 패턴을 기준으로 3의 제곱인 수가 들어오면

 

3짜리 패턴을 3처럼 출력한다 생각하면 편하다

 

그럼 27은 3출력한다((3짜리패턴을)3짜리처럼)로 이해할수있다

 

그럼 간단하다 일단 3이 나오는 패턴을 for문으로 만들어보자

 

for i in tmp

for i in tmp:         struc.append(i*3)     for ii in tmp:         struc.append(ii+' '*(n//3)+ii)     for iii in tmp:         struc.append(iii*3)

n이 3이면 i//3은 1이다

 

그럼 첫 포문은 ***

두번쨰 포문 * *

세번쨰는 첫번째와 같이 ***

 

여기서 현혹되지말자 

 

우리는 "이 식을가지고 재귀를 돌릴것이다"

 

먼저 재귀식을 27일때 9일때 3일때라는 스택을 가진 재귀를 짜보자

def star(n):     if n ==1: return ['*']         struc = []     tmp = star(n//3)

이러면 자연스레 star라는 재귀는 이런식으로 쌓인다 

 

star(n//3) star(star(n//3)//3) start(star(n//3)//3)//3)

 

그럼 뒤에서부터 1이되었을때*을 리턴한다 

 

*이 리턴되면 팩토리얼에서 1이 리턴됐을때 역순으로 쭉 계산하면서 올라가듯

1일때정보 > 2일때정보

 

마찬가지로

 

*일때 정보

 

*가 for문을 돈 정보

 

*가 for문을 돈 정보가 for문을 돈 정보가 리턴된다

 

그럼 3일때의 정보가 9일때 재활용, 27일때 재활용해서 값이 튀어나오게된다

 

..

 

사실 나도 처음부터 이 코드가 떠오른건 아니다

 

인터넷 검색해서 수많은 코드를 본 뒤에 이게 제일 이해가 쉽고 편하고 재귀에대한 설명으로 제일 편한게 이게 아닐까해서 이걸 가져오고 계속 보고 또 봤다

 

결국 왜 이렇게 돌아가는건지 이해는 가긴 갔는데 ..

 

팩토리얼을 처음볼때 처럼 몇주정도 지나야 한방에 이해가 될 듯 하다

 

 

 

다음편은 .. 하노이탑으로 보낼듯한데 

 

문제보니 벌써 현기증이온다

 

화이팅이다 ..