[ python ] 코드업 1901 - 1부터 n까지 출력하기

📍 코드업 1901 - 1부터 n까지 출력하기

코드업 1901 - 1부터 n까지 출력하기

⚡️ 나의 풀이

재귀함수 문제 중 같은 문제라도 1부터 n까지 구하는 문제가 있는 반면, n부터 1까지 역순으로 구하는 문제도 있다.

재귀함수에서 알아두어야 할 자료구조는 스택(stack)이다. stack의 특성 상 재귀함수는 나중에 들어온 값이 제일 먼저 나가게 되는 후입선출(LIFO)구조인데, 여기서도 제일 마지막에 호출한 함수를 제일 먼저 호출하는 과정을 거친다.

이 문제는 1부터 n까지 구하는 문제인데, 함수의 호출 순서를 알고 싶어 print(f(n))을 설정했다.
또 마지막에 return을 적지 않아도 되지만, 어떠한 흐름으로 진행되는지 알고싶어 명시적으로 적었다.

전체적인 흐름은 다음과 같다.

입력값에 5가 들어오게 되면 5는 1과 같지않으므로 bottom_up(4)를 호출하게된다. bottom_up(4)는 1과 같지않으므로 bottom_up(3)를 호출하게 되고 마지막으로 n이 1일 때는 print(n)을 거치고 return을 하게된다. return을 할 때는 스택에 호출됐던 함수들을 다시 찾아간다(밑에서부터) bottom_up(1)을 호출한 n=2는 print(n)을 하게되고 또 다시 올라가게된다. 결과적으로 print는 1에서부터 n까지 출력하게 된다.

n	stack	print
5	bottom_up(4)	5
4	bottom_up(3)	4
3	bottom_up(2)	3
2	bottom_up(1)	2
1	1	1

하단에 사진은 재귀함수 호출의 흐름을 화살표로 그려봤다.

def bottom_up(n):
    print(f'f({n})', end=' ')
    if n != 1:
        bottom_up(n-1)
    
    print(f'f({n})', n)
    return

bottom_up(5)

👉🏽 
f(5) 
f(4) 
f(3) 
f(2) 
f(1) f(1) 1
f(2) 2
f(3) 3
f(4) 4
f(5) 5

---