[TIL] 알고리즘 : Recursion

1. 재귀 함수 (Recursion Function)

어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.
"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."

"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."

"재귀함수가 뭔가요?"
"재귀함수는 자기 자신을 호출하는 함수라네"
"라고 답변하였지."

"라고 답변하였지."

"라고 답변하였지."

• 함수의 선언이 끝나기 전에 자기 자신을 다시 호출하는 함수
• 무한 루프에 빠질 수 있기 때문에 하나의 자기 자신을 호출하지 않는 종료 조건이 존재해야 한다.
• 모든 Case는 종료 Case로 수렴해야 한다.
• 파이썬은 함수 깊이 제한이 1000으로 기본설정 되어 있어 에러가 발생한다

<무한루프 예시>

def Recursion(n):
  print (n)
  Recursion(n-1)
  
Recursion(10)

<결과>

2. 재귀함수 VS 반복문

모든 재귀 호출은 반복문으로 변경 가능하며 모든 반복문도 재귀 호출로 변경 가능하다.

• Recursion의 장점

  • 가독성이 뛰어나다. 복잡한 알고리즘을 간결하게 작성할 수 있다.
  • 변수를 적게 사용해 오류가 발생하는 가능성을 줄인다.
  • 반복문의 중첩이 많이 필요할 수록 재귀 함수를 사용하는 것이 간결하다.

• Recursion의 단점

  • 재귀 호출을 하게되면 함수 호출 횟수가 커질 수 있다.
  • 재귀 함수 호출시 메모리에 너무 많은 Stack이 쌓일 경우 StackOverFlow가 발생한다.
  • 반복문 보다 시간을 더 소모한다.

3. 팩토리얼 (Factorial) ❗️

• 반복문으로 구현

def factorial(n):        
    result = 1
    # 1부터 n까지의 수를 차례대로 곱하기
    for i in range(1, n + 1):
       result * = i
    return result

print(factorial(5))
실행결과 >>> 120

• 재귀 함수로 구현

# 재귀함수
def factorial(n):
    if n == 1:      # n이 1일 때
        return 1    # 1을 반환하고 재귀호출을 끝냄
    return n * factorial(n - 1)    # n과 factorial 함수에 n - 1을 넣어서 반환된 값을 곱함
 
print(factorial(5))
실행결과 >>> 120

4. 피보나치 수열 (Fibonacci numbers)

• 반복문으로 구현

def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a
print (fib(8))

실행 결과 >>> 21

• 제너레이터로 구현

def fib(n):
    a, b = 0, 1
    for i in range(n+1): #제너레이터를 구현하면 0부터 n번째 까지 값을 순차적으로 받기때문에 n+1 을 해준다 
        yield a
        a, b = b, a + b
fib = fib(8)
for i, val in enumerate(fib):
    print('Fibonacci({}): {}'.format(i, str(val)))

실행결과 >>>
Fibonacci(0): 0
Fibonacci(1): 1
Fibonacci(2): 1
Fibonacci(3): 2
Fibonacci(4): 3
Fibonacci(5): 5
Fibonacci(6): 8
Fibonacci(7): 13
Fibonacci(8): 21

• 재귀 함수로 구현

def fibo(n):
    if n <3 : 
        return 1
    else :
        return fibo(n-1)+fibo(n-2)
        
#1 1 2 3 5 8 13 21 34  < 결과값
#1 2 3 4 5 6 7  8  9  < 순서

print(fibo(8))
실행결과 >>> 21

참고 자료(References)

https://dojang.io/mod/page/view.php?id=2353
https://psychoria.tistory.com/770
https://ansohxxn.github.io/algorithm%20lesson%201/chapter1-1/
https://freedeveloper.tistory.com/371