Recursive
오늘은 파이썬 알고리즘 기초인 재귀 용법에 대해서 알아보겠습니다.
먼저 재귀란 무엇이고 어떤 방식으로 진행되는지에 대해서 그림을 머릿속에 그려보아야 합니다.
오늘 포스팅에서는 컴퓨터가 어떤 방식으로 함수를 호출하고, 호출한 함수를 다루는지에 대해서 설명하겠습니다.
이번 포스팅에서는 먼저 코드를 보여주고 코드를 따라서 어떻게 함수가 호출이 되고, 호출된 함수가 계산이 되어지는 것에 대해서 설명하겠습니다.
재귀 용법을 활용한 알고리즘 풀이는 대표적으로 피보나치 수열과 하노이 탑이 있는데, 뭔가 제 생각에는 처음 배우는데 있어서는 좋은 예제라는 판단이 들지 않아서, 2진수로 바꾸는 것은 재귀용법(Recursive)를 이용해서 설명해보려고 합니다.
10진수를 2진수로 변경해보자
위 사진을 참고하면 결국 값은 1 1 1 0 이 나오게 된다.
그 값은 2^3 + 2^2 + 2^1 로 8 + 4 +2 =14 라는 값이 나오게 됩니다.
어떻게 동작하는 것인가?
사진을 보면 함수를 호출하고 컴퓨터에서 중간에 다른 함수를 만나게 되면 STACK에 저장을 하고 새 함수를 호출하게 됩니다.
그렇다면, 우리가 원하는 것을 만들어 내기 위해서는 0을 계속 2로 나누는 것을 방지 해야하므로 결국 우리는 끝내는 지점을 0에서 끝내게 되는 것입니다. 그래서 0을 만나게되면 재귀 호출을 끝을 내고 차례로 회수를 해야합니다.
14 / 2 - 0<
7 / 2 - 1<
3 / 2 - 1<
1 / 2 - 1< 원하는 값들
0 / 2 --?(이때는 끝내야지)
답은 1110(2)
그렇다면 0을 만나게 되면 그때부터 차례로
1 % 2 -> 3 % 2 -> 7 % 2 -> 14 % 2의 값을 호출하면서, 함수의 스택에서 탈출하기 시작합니다.
그러면 1 -> 1 -> 1-> 0 이렇게 프린트를하게 됩니다.
source code
def RECURSIVE(x):
if x==0:
return
else:
RECURSIVE(x//2)
print(x%2)
if __name__=="__main__":
RECURSIVE(14) 