[Algorithm] 재귀 함수와 리턴(return)

개요

그래프 알고리즘(DFS, BFS)와 백트래킹, 동적 계획법(DP)와 같이 주요 알고리즘을 공부하며 어려움을 느꼈습니다. 그래서 오늘은 재귀 함수와 리턴(return) 개념에 대해 확실하게 다시 정리하려 합니당 

 

 

 

 

 

재귀 함수란?

: recursion, 정의 단계에서 자기 자신을 재 참조하는 함수

: 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법 이다.

https://www.youtube.com/watch?v=3DNaj8R4HJg

위 사진은 예전에 유명했던 밈이다. 재귀함수를 떠올리다 생각나 한번 넣어보았다 🤣

Abbott: 1루수가 누구야?
Costello: 맞아, 1루수가 누구야.
Abbott: 그래, 1루수가 누구야.
Costello: 그래 맞아, 1루수가 누구야.
Abbott: 내가 말하는 거 이해 못하는 거야?
Costello: 제가 무슨 말씀인지 아주 잘 알아듣고 있습니다. 1루수가 누구야 라고 물어보셨죠?
Abbott: 그래, 1루수가 누구야?
Costello: 네, 맞습니다. 1루수가 누구야. “““

# 재귀함수 예제 0~n까지의 합계 구하기
def sum(n): 
    if n == 0: 
        return 0
    return n + sum(n-1) 
sum(4) # 10

• 재귀 함수에서 가장 중요한 것은 종료 조건을 설정하는 것이다. 위 예제에서의 종료조건은 n이 0일 때이다.
• 값을 반환하지 않는 함수에서, 해당 함수를 종료하고 싶을 때 값 없이 return을 적어주면 되며, 이는 함수의 가장 끝에 도달했을 경우에도 알아서 함수는 return을 하며 빠져나오게 된다 !

 

 

 

 

 

 

return

: 현재 함수를 끝내거나 결과 값을 돌려주기 위한 키워드

→ 돌려주는 값이 없는 경우는 임의의 조건을 만족했을 때 탈출하기 위함이고,

→ 돌려주는 값이 있는 경우 return 키워드를 사용하여 돌려줄 값을 명시한다 !

🎇“함수를 실행했던 위치로”, “함수를 끝내자”🎆

 

 

 

 

 

 

 

 

재귀함수에서의 POINT

def print_star(n):    # 1부터 n번째 줄까지 별을 출력하는 함수
    if n == 0:        # n이 0이라면, 더 이상 진행하지 않고
        return        # 퇴각합니다.

    print_star(n - 1) # 1부터 n - 1번째 줄까지 출력하는 함수
    print("*" * 5)    # n번째 줄에 해당하는 별 출력

print_star(3)

#출력 값
#*
#**
#***

우리가 집중해야할 부분은 함수가 return을 하며 빠져나올 때, 함수가 어디로 퇴각하는지이다 !

💡 Why? 대입되는 숫자는 3→2→1 내림차순으로 입력되는데 별은 1→2→3 순서로 찍힐까 ?
-> Call Stack 개념을 이해해야한다 !

1. print_star(3) 이 호출됩니다.
2. print_star(3) 함수가 콜 스택에 push됩니다.
3. n은 3이므로 n == 0이 False입니다. 따라서 print_star(n - 1) 이 호출됩니다.
4. print_star(2) 함수가 콜 스택에 push됩니다.
5. n은 2이므로 n == 0이 False입니다. 따라서 print_star(n - 1) 이 호출됩니다.
6. print_star(1) 함수가 콜 스택에 push됩니다.
7. n은 1이므로 n == 0이 False입니다. 따라서 print_star(n - 1) 이 호출됩니다.
8. print_star(0) 함수가 콜 스택에 push됩니다.
9. n은 0이므로 n == 0이 True입니다. 따라서 return문이 실행되어 print_star(0) 함수가 콜 스택에서 pop됩니다. (종료조건)
10. print("" * 5) 가 실행되어 첫 번째 줄에 1개의 별이 출력됩니다.
11. print_star(1) 함수가 콜 스택에서 pop되고, print("" * 5) 가 실행되어 두 번째 줄에 2개의 별이 출력됩니다.
12. print_star(2) 함수가 콜 스택에서 pop되고, print("*" * 5) 가 실행되어 세 번째 줄에 3개의 별이 출력됩니다.
13. print_star(3) 함수가 콜 스택에서 pop되면서 프로그램이 종료됩니다. 

 

 

 

 

 

 

 

 

 

📌 정리

Call Stack개념을 제대로 이해하지 못하면, 재귀 함수 또한 제대로 이해할 수 없다는 것을 알 수 있었다 ㅠㅅㅠ

사이사이 기본 적인 개념에 구멍이 있다는 것을 알게 되었고 조금 더 기본에 충실할 수 있도록 해야겠다.