TIL 27. What is Recursion?

Today's topic

학창 시절 수학 시간에 factorial이라는 개념을 배우고 문제를 해결할 때 사용했었다. 이러한 개념을 programming 언어로도 구현이 가능하다고 한다. 해당 개념을 recursion(재귀)라고 하는데, 알고리즘 적으로도 중요한 개념이기에 이번 post를 통해 알아보고자 한다.

👉 What is recursion?

우리나라 말로 하면 재귀이다. recursion(재귀)는 programming에서는 함수가 자기 자신을 호출할 때 쓰는 용어이다.

👉 Recursion의 조건?

함수가 무한대로 호출되지 않도록 하는 base case(기저 조건)이 있어야 한다. 만약 base case를 지정하지 않으면 함수가 무한대로 호출이 되고 결국에는 메모리 과부하(stack overflow)로 error가 나게 된다.

👉 Recursion은 언제 사용할까?

Recursion(재귀)는 for문과 같이 roof를 사용할 수 있는 경우라면 대부분의 경우에 사용할 수 있다. Recursion(재귀)는 코드의 가독성을 높이기 위해 사용하나 그렇다고 무조건 roof 보다 더 효율적이거나 나은 방식은 아니다.

👉 Recursion의 동작 원리?

Recursion의 작동원리는 stack을 사용한다. Stack이란 임시 데이터를 처리할 수 있는 간결한 도구인데 여기에 3가지 제약이 있다. 데이터는 stack의 끝에만 삽입할 수 있고, stack의 끝에서만 삭제할 수 있다. 마지막으로 stack의 마지막 원소만 읽을 수 있다.

출처 : stackoverflow

위의 그림은 전형적인 recursion의 하나인 factorial의 동작에 대한 예시(factorial(4))이다.
factorial(4)의 경우 factorial(4)함수 안에 factorial(3), factorial(2), factorial(1)이 차례대로 함께 실행이 된다. 가장 먼저 실행되는 함수 부터 밑에 쌓이고 제일 마지막에 실행되는 함수가 위에 쌓이게 된다. 반대로 종료될 때는 제일 위에 있는 함수 부터 종료되고 가장 아래에 있는 함수가 가장 나중에 종료 된다. 따라서 factorial(n) 함수는 factorial(n-1) 함수가 작동 끝나기 전까지는 종료가 안되기 때문에 factorial 함수가 실행이 되는 원리이다.

다음은 recursion의 대표적인 경우인 Factorial과 Fibonacci numbers가 있다. 아래에서 예시 code로 작성해 보고자 한다!

👉 Factorial!

def factorial(number) : 
    if number == 1 :
    	return 1
    else :
    	return number * factorial(number-1)	

👉 Fibonacci numbers

def FibonacciNumbers(n) : 
    if n <= 1 :
        return n
    elif n >= 2 :
        return FibonacciNumbers(n-1) + FibonacciNumbers(n-2)

print(FibonacciNumbers(0)) #0
print(FibonacciNumbers(1)) #1 
print(FibonacciNumbers(2)) #1
print(FibonacciNumbers(3)) #2
print(FibonacciNumbers(4)) #3
print(FibonacciNumbers(5)) #5

My opinion

Programming 언어로 이렇게 대표적인 recursion인 팩토리얼과 피보나치 수를 나타낼 수 있다는 게 신기했고, 잊혀져가던 수학적 개념들을 한 번 수면 위로 떠오르게 할 수 있어서 좋았다!