3. Recursion

대학교 2학년 때 자료구조/알고리즘 시간에 배웠던 재귀가 생각났다. 그때는 왜 이런 걸 배우지하면서 이냥저냥 수업듣고 그랬는데 이제보니 기본기를 다질 수 있는 매우 귀중한 시간이었던 것 같다. 

그때 공부 제대로 안한 벌을 군대와서 받는....

 

무튼무튼 잡담은 여기까지하고,

이번 글에서는 재귀에 대해 알아본 뒤, 간략하게 재귀를 배울 때 항상 등장하는 문제인 하노이의 탑을 풀어보도록 하자.

 

 

1. Recursion

재귀(Recursion)는 본인을 호출하는 메서드이다.

 

 재귀는 어떤 목적을 달성하기 위해 본인, 자기 자신을 스스로 호출하는 방법이다.

재귀에 대한 개념을 알면, 외관상 코드로만 보면 간결해보이는 이중 for loop보다 더 효율적인 알고리즘을 설계할 수 있으며, 다음 글에서 살펴볼 내용인 브루트-포스(Brute-force Algorithm)와 백트래킹(Backtracking) 알고리즘을 이해하는데 기본이 되는 주제이다.

 

 

2. Repetitive algorithm에서 나타낼 수 있는 2가지 접근

1. iteration

- loops(for, while, do-while)

 

2. recursion

- 함수가 자기 자신을 계속해서 반복하여 호출하는 방법

- 문제를 breaking down 하기에 적절한 방식

(break down : 주어진 문제를 더 작은 크기의 문제로 줄이는 행위)

 

- 많은 경우에 알고리즘을 대폭 단순화시킨다.

- 어떤 문제를 해결하려 할 때 그 문제에 recursion을 적용할 수 있는 경우가 있고 아닌 경우가 있는데, 만약 적용할 수 있는 경우에 그 문제를 엄청나게 간단하게 만들어 준다.

 

+) 팩토리얼을 iteration과 recursion 두 가지 방법으로 구현해보자.

1. factorial code with iteration

 

def factorial(n):
    if n == 0:
        return 1
    else:
        ans = n
        for i in range(n-1, 0, -1):
            ans *= i
        return ans

num = 7
print(f"{num}! = {factorial(num)}")
# 7! = 5040

 

 

2. factorial code with recursion

 

def factorial(n):
    if n == 0:
        return 1
    else:
        ans = n*factorial(n-1)
        return ans

num = 7
print(f"{num}! = {factorial(num)}")
# 7! = 5040

 

 

recursive 함수의 핵심은 다음 두 가지 경우가 존재하야 한다는 것입니다.

 

1. Base cases : 계산을 안 해도 한번에 답이 바로 나오는 경우(위의 factorial 예시에서 n = 0 일 때 1 인 상황)

- 회귀가 기본 조건을 만족하기만 하면 멈추게 될 것을 의미함.

- 사실상 이부분은 계산이 아니라 미리 정해진 정의에 가깝다.

 

2. Recursive cases : 함수 호출을 종료시킬 수 있는 조건이 있는 경우

- 함수가 자기 자신을 호출하여 기본 조건(base cases)을 성취하는 방향으로 진행하는 것.

 

 

recursion은 호출하는 횟수만큼 memory를 많이 잡아 먹는다는 문제도 있다.

 

 

 

3. Complexity of recursive algorithms

recursive algorithm의 order(차수)를 정의하는 것은 recursion의 order를 결정하는 문제와 그 문제의 recursive method body의 order를 곱하는 것에 대한 문제입니다.

 

이 어려운 말을 멱함수(power function)를 통해 알아보자면,

def power(base, exponent): # f(n) 
    # c
    if exponent == 0:
        return 1

    # f(n-1)
    else:
        return base * power(base, expoenet-1)


a, b = 5, 3
print("%d**%d = %d" %(a, b, power(a, b)))

이 예제에서는 n+1이 recursion의 차수(order), O(1)이 recursive method body의 차수가 되겠다.

 

 

 

 

 

 

* Reference

https://cdragon.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Recursion-and-Backtracking%EC%9E%AC%EA%B7%80-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9?category=1070664

[자료구조와 알고리즘 | 파이썬] Recursion and Backtracking(재귀 & 백트래킹) + Divide and Conquer(분할정복)

 

 

 

https://coding-potato.tistory.com/21

[python] 재귀함수 파헤치기