재귀함수 구조

 

문제출처 : 코드업 재귀함수 문제집 (파이썬으로 풀이) https://codeup.kr/problemsetsol.php?psid=21

 

---

 

  반복문 다음에 (for문, while문...)

재귀 함수가 배울 때, 가장 먼저 나오는게 <<팩토리얼 함수.>>

그런데 이 코드 몇 번 보다보니 외워져서 재귀를 알고 있다고 생각했는데...!

그 외 코드업에서 재귀함수 기초 문제를 스스로 생각해서 풀어보려니 막막!!

아 모르고 있었구나. 또 안다고 착각했구나. 눈물 또르르

 

 재귀가 익숙해야 이걸로 DFS 재귀 코드도 짜보고

분할정복도 해보고

불필요한 반복 구조를 줄이는 DP(dynamic programming)의 메모이제이션도 하는...

연결고리를 만들어 가나보다. (그냥 다 다른 건 줄 알았는데 상관관계가 조금씩 보이는 중)

 

수업 과정으로는 성큼성큼 배워서 ( 왜 이리 찰나처럼 스쳐갔는지.. )

팩토리얼만 봤는데 바로 재귀로 부분집합, 순열을 하라고... 응?응???

그 사이의 기초를 내가 다시 몸으로 부딧치며 구슬들을 매꿔야 했다.

머리로 안 돌아가면 손으로 과정들 그리면서 배우는 중

 

---

* 도움을 받는 것 몇가지를 언급해보자면

1. 반복문은 재귀로, 재귀는 반복문으로 구현 가능하다.

2. 재귀함수를 작성 할 때는, (1) base case (2) recursive case 를 분리해서 짜기

 

-재귀 연습으로 짰던 문제를 반복문으로 풀어보려고 하면서, 어느 순간 반복문을 생각하기가 더 어려운 케이스가 

나오며, 슬슬 재귀랑 빨리 친해지는게 신ㅅ상에 좋.. 

---

내 표현 : 재귀 속 재귀 = 내려간다. 들어간다, 깊어진다 

            리턴해서 = 올라온다, 돌아나온다, 빠져나온다

 

[ 재귀에 대한 개념 ]도 알다가도 모르겠고 깊어진다는게 뭔지 감각이 안 왔는데,

나름 생각하기는 

 

영화 인셉션에서 (2)재귀의 영역은, 나오는 <꿈 속의 꿈>, 꿈 속의 꿈 속의 꿈 .... 이고, 

(1) 베이스 케이스 이자 재귀가 마지막에 도달해서 빠져 나오는 조건은, 그 영화의 <킥> 이라고 봤다.

 

재귀가 마지막에 갈 때까지 깊어져 내려가다가 (1)base case 나 뭐 다른 조건으로 뻥차여서

위로위로 끌려 올라오는 현상이라고 봤다. 그래서 내가 짠 재귀가 어떻게 해야 정.말.바닥에 닿는지 확실히 알아야 한다. 

 

TMI  예를 들어 기초적으로 > 팩토리얼의 경우 0! = 1 이고 1! = 1 이다. 1!를 0!x1로 생각할 수 도 있다.

n-1해서 0까지 도달할지 1까지 도달할지를 내가 정하는 것. 

>피보나치의 경우도 1번째 1, 2번재 2로 (1 1 2 3 5 8 ....) 로 많이 설명하여 n-1과 n-2를 해서 내려갈 때  (1)base case로 n<=2 이면 1이다. 로 많이 하기도 하는데,

나는 0번째는 0, 1번째는 1을 베이스로 삼아서 (0 1 1 2 3 5 8...), 2번째가 = 0번째+1번째로 봤다. 

리스트나 튜플 등등의 인덱스를 할 때, 0부터 시작하므로 결과값을 도출할 때, 더 생각하기가 수월해서 

기본적으로 가능한 0부터 하려고 한다. 마무리로 +1 -1 고려하는게 왜이리 가끔 헷갈리는지...TMI  

 

 

또, 영화에서 왜 꿈속으로 들어가냐면 <현실의 기억이나 감정을 바꾸기 위해서> (*스포인가..?) 인데

문제에서, 경우를 따져봐서 최대값이나 최소값을 구하거나 할 때를 보면 

함수 내의 파라미터나 global 변수로 어떤 값을 찾아 내곤 한다. 

이건 마치 꿈 속의 꿈 속의 꿈..에 들어 갔다가, 나올 때는 (들어가면서 바꾸거든 나오면서 바꾸거든)

<가장 밖의 현실 영역에 영향을 미치는 것>이라고 봤다.

 

그냥 함수 구조를 보면

return 에 아무 값도 없는 None 인 경우랑

return ~~ 써진게 있는데.

 

재귀함수에서 return~~ 하면 이건 재귀에서 빠져 나올 때, 즉 한 꿈에서 깰 때,

꿈 속에서 무언가(물건)을 가지고 나오는 형태 ㄷㄷ 라고 이해했다.

you know... 알..알겠죠? 무슨느낌인지? (옛날에 그런 이야기가 있었다...)

return None 하면 빈 손으로 꿈 속을 빠져 나오는 것이고.   

 

---

 

자, 코드에 적용하자.

 

내 표현 : 재귀 속 재귀 = 내려간다. 들어간다, 깊어진다

            리턴해서 = 올라온다, 돌아나온다, 빠져나온다 라고 이것저것 작성하며 표현했지만,

 

그냥 이미 코드자체가 1행부터 ..< 위에서 아래로 내려가고 >있는 형식이여서

재귀 속의 재귀를, 2차원 종이에 그림으로 그릴 때도 단계단계 (위에서 아래로 내려가는 모습)으로 그리곤 해서... 처음에 헷갈릴 땐 별게 이것도 헷갈렸는데....

 

재귀 속에 들어가는 깊어지는 표현을

상->하(아래를 뚫고 들어가는) 이미지보다는 

(벽을 뚫고 들어가는) 내 모니터를 뚫고 안으로 움푹 들어가는 이미지로 

코드의 흐름과 이를 구분하려고 했다. 

(코드는 시간의 흐름, 재귀는 공간의 흐름 같은 구분...( 별개인데 또 별개가 아닌 느낌적인 느낌  )

 

 

-끝.

내일은 오늘보다 재귀를 더 잘 알고 사용할 수 있기를

 

---

 

https://blog.fupfin.com/?p=150

자바 프로그래머에게 재귀는 왜 어려운가?