자료구조와 알고리즘 - 재귀함수(Recursion)

 

재귀함수에 대해서 알아보자

 

재귀함수의 정의

컴퓨터 과학에 있어서 재귀(再歸, Recursion)는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻하며, 이를 프로그래밍에 적용한 재귀 호출(Recursive call)의 형태로 많이 사용된다. 또 사진이나 그림 등에서 재귀의 형태를 사용하는 경우도 있다.  

 

 

재귀함수의 장점

• 먼저, 알고리즘 자체가 재귀적인 표현이 자연스러운 경우에는 재귀 함수를 쓰는 것이 큰 도움이 됩니다. ...
• 두번째로, '변수 사용'을 줄여주어 mutable state가 취할 수 있는 경우의 수를 줄여주게 됩니다.

📌출처: https://velog.io/@tilsong/%EC%9E%AC%EA%B7%80-%ED%95%A8%EC%88%98%EB%8A%94-%EC%96%B8%EC%A0%9C-%EC%8D%A8%EC%95%BC-%ED%95%A0%EA%B9%8C

 

 

재귀함수 코드 분석

1. 팩토리얼을 중심으로.. 

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

재귀함수로 factorial 함수를 만든 코드를 설명한 그림

2. 피보나치 수를 중심으로..

def fibo(n):

    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibo(n-1) +fibo(n-2)


n = int(input())
print(fibo(n))