Recursion (재귀호출)

재귀호출(Rescursion) 개념

  재귀(Recursion) : 함수가 자기 자신을 호출하는 방식

  스택(Stack) 구조를 사용하여 동작

  종료조건을 만나면, 스택에서 하나씩 꺼내며 연산 수행

 

시작점과 종료 지점을 잘 정해야 한다.

def factorial(n):
    if n == 1:  # 종료 조건 (Base Case)
        return 1
    return n * factorial(n - 1)  # 재귀 호출

 

factorial 실행흐름

factorial(5) → 5 * factorial(4)
factorial(4) → 4 * factorial(3)
factorial(3) → 3 * factorial(2)
factorial(2) → 2 * factorial(1)
factorial(1) → 1  (Base Case 도달)

 

스택구조

factorial(5)   (대기)
factorial(4)   (대기)
factorial(3)   (대기)
factorial(2)   (대기)
factorial(1)   (반환 시작)

 

언제 재귀를 써야 하고 언제 반복문을 사용해야 하나요?

 

모든 재귀는 반복문으로 구현이 가능하다. (이론적으로)

심지어 재귀보다 반복문이 빠르다.

 

그렇다면 반복문이 더 빠르면, 재귀를 사용하지 않아도 되는 거 아니야?

 

하지만, 재귀로 풀면 엄청 간단하데, 반복문으로는 엄청 복잡한 게 있다.

  ex) 하노이 탑 문제, 미로 문제

 

그래서 재귀 함수 코드가 훨씬 직관적 + 간단하게 구현 대신 느리다.

 

그래서 어떤 문제가 재귀 함수로 풀면 쉬울까?

 - 시작 점 ~ 목표지점까지 진행한다.

 - 목표지점까지 갔다가 돌아오면서 무언가를 수행해야 한다. 혹은 중간 지점까지 왔다가 다시 end로 간다.

 

왜 간단하게 풀릴까?

진행하면서 나오는 구조가 동일하다.

---

 

백준 10872번 : 팩토리얼

https://www.acmicpc.net/problem/10872

 

N = int(input())

def factorial(N):
    if N == 1:
        return 1
    else:
        return N * factorial(N-1) # 재귀호출

print(factorial(N))

팩토리얼의 호출과 반환 (출처 : 코딩 도장)

 

 

모든 배열의 요소에 접근하는 재귀함수

def f(i, N): # i 배열 인덱스, N 배열 크기
    if i == N : #탈출 조건
        return
    else: # 재귀호출
        print(A[i])
        f(i+1, N)

A = [1,2,3]
f(0,3)

 

배열에 x 가 있으면 1, 없으면 0을 리턴하는 재귀함수

def f(i, N, v): # i 배열 인덱스, N 배열 크기
    if i == N :
        return 0
    elif arr[i] == v:
        return 1
    else :
        return f(i+1,N, v)

arr = [1,2,3]
v = 3
print(f(0,3, v))