재귀 함수란? (재귀 함수 이해, 재귀란?, 재귀 함수 정의, 재귀 함수 팁)

재귀 함수란?

---

• 재귀란 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘
• 함수의 return 값을 반복적인 함수동작으로 가공할때 사용
• 마치 도미노가 넘어지는 모습에 비유 가능
• 수학적 귀납식을 코드로 바로 옮길 수 있는 장점

예시

---

# 바킹독 1~N까지 합 재귀 연습


def ssum(N):
    if not N:
        return 0
    return N + ssum(N-1)

N = int(input())
print(ssum(N))

# 바킹독 N~1까지 출력 재귀 연습

def pprint(N):
    if N == 0:
        return
    print(N)
    pprint(N-1)


N = int(input()) 
pprint(N)

이런 식으로 동작 가능

여기서

if not N:
    return 0

와

if N == 0:
    return

부분을 Base-condition 이라고 하는데, 재귀 함수를 호출 할 때 무한 재귀 발생을 막기 위해서는 꼭 필요하다.

• 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료 되어야함(재귀 탈출 조건문, base-condition)
• 모든 입력은 base-condition으로 수렴해야함

재귀에 대한 정보

1. 함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 설정
2. 모든 재귀 함수는 반복문으로 표현 가능
3. 재귀는 반복문으로 구현했을 때에 비해 직관적이고 코드가 간결하지만 메모리/시간에서는 비용이 비쌈 (시간/공간 복잡도) -> Stack Frame이 쌓이기 때문
4. 한 함수가 자기 자신을 여러번 호출하게 되면 비효율적의 끝판왕이 됨 (ex. 피보나치 수열을 재귀로 나타낸 함수에 입력값이 커질 때)

Example

def fibo(n):
    if n<=1:
        return 1;
    return fibo(n-1) + fibo(n-2)

이코드는 피보나치 수열을 구하는 귀납적인 점화식을 그대로 구현 한것이지만,
한 함수에서 여러번 호출하게 되며 이 함수는 그래프의 끝으로 갈수록 기하학적으로 많아짐.
이미 계산한 값을 계속 계산하는 동작이 됨
-> fibo(n-1) + fibo(n-2)

5. 재귀 함수가 자기 자신을 부를 때 스택 영역에 계속 누적이 됨 (StackFrame)
   

재귀 함수를 작성 하는 요령

• 함수의 정의
  • 함수가 어떤 인자를 받는지 정의 -> 기준점과 방향을 설정할 수 있는 인자
  • 어떤 역할을 수행하는지 정의 -> 받은 인자를 내부적으로 어떻게 이용 할 것인지
• Base-condition
  • 재귀가 어떤 조건에 탈출해야 할지 생각
• 재귀 식 정의
  • 재귀 함수의 내부 구현
  • Base-condition 위치 조정 등

재귀는 절차지향 적인 사고를 버려야 한다 !!

• 귀납적 사고를 하도록 노력
• 코드를 짜고 머릿속으로 스택 프레임을 전부 그려볼 생각을 하지말고 믿어라 !!
• 도미노 식의 연산 동작을 하는 것 같으면 -> 재귀로 구현이 가능하다

Ref.

• https://www.youtube.com/watch?v=8vDDJm5EewM
• https://www.secmem.org/blog/2021/07/09/recursion/