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

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

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

---

⚡️ 나의 풀이

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

 

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

 

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

 

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

 

1. 입력값에 5가 들어오게 되면 5는 1과 같지않으므로 bottom_up(4)를 호출하게된다.

2. bottom_up(4)는 1과 같지 않으므로bottom_up(3)를 호출하게 되고 마지막으로 n이 1일 때는 print(n)을 거치고 return을 하게 된다.

3. return을 할 때는 스택에 호출됐던 함수들을 다시 찾아간다(밑에서부터) bottom_up(1)을 호출한 n=2는 print(n)을 하게 되고 또다시 올라가게 된다. 결과적으로 print는 1에서부터 n까지 출력하게 된다. 하단에 재귀 함수 호출의 흐름을 화살표로 그려봤다.

 

 

728x90

 

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