재귀함수

재귀 (명사)
원래의 자리로 되돌아가거나 되돌아옴. 예) 재귀본능

즉, 함수 안에서 자기 자신을 다시 호출하여 작업을 수행.

재귀로서 문제를 해결하려면, 아래 2가지를 유의해야 한다.
1. 내 함수와 서브함수와의 관계 (재귀의 시점)
2. 종료되는 시점을 정의 (base case)

---

sum 함수를 반복문 없이 만들어보자

sum 함수에 인수 n을 넣으면 1부터 n 까지의 총합을 계산한다. 이때 sum(7)이라면 7을 인수로 넣으면 1부터 7까지를 더하는데, 내 함수와 서브함수와의 관계로 생각하자면 sum(7) = sum(6) + 7 이 되는 것이다. 그리고 마지막 종료는 인자가 1인 순간으로 알려줘야 한다.

재귀 함수를 작성하면, 결국 함수의 과정에서 정의하고 있는 함수를 다시 부르게 되므로 종료 순간을 맨 위에 조건문을 걸어 명시한다.

def sum(n):
	#종료 시점 명시
    if n == 1: 
    	return 1
	
    #내 함수와 서브함수의 관계를 통해 규칙성을 통해 재귀
	return sum(n-1) + n

피보나치 수열을 만들어보자

피보나치 수열은 처음 두 수 이후의 각 숫자가 앞의 두 숫자의 합인 일련의 숫자이다. 아래처럼 진행된다.

0, 1, 1, 2, 3, 5, 8 ...

수학적 정의는 F(n) = F(n-1) + F(n-2)이다. 즉, 이게 재귀함수에서 내 함수와 서브함수와의 관계가 된다. 그리고, 초기 값인 0, 1 을 초기 조건이자 종료 조건으로 넣으면 된다.

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

print(fibo(10))

---

재귀 함수는 n 값이 커질 수록 느려지고, 비효율적이라는 점을 유의해야 한다.
함수를 지속적으로 호출하여 스택을 쌓는 것으로 메모리가 계속 할당되기 때문에, 재귀 함수를 사용하다가 무한루프에 빠지거나 너무 많은 호출로 인하여 콜스택이 쌓이면서 스택 오버플로 현상이 발생할 수 있다.

• 콜스택(call stack) : 함수가 호출될 때 사용되는 임시 저장 메모리
• 스택 오버플로 오류(StackOverFlowError) : Stack 영역의 메모리가 지정된 범위를 넘어갈 때 발생하는 오류
• 파이썬에서는 콜스택을 1000개 까지 허용

재귀함수로 풀 수 있는 문제는 반복문으로도 풀 수 있으므로, 콜스택이 쌓이는 문제가 있을 경우에는 반복문 사용하자! (각 상황에 맞는 적절한 풀이를 쓰는 것이 중요)

---

추가로, 백준에 있는 N과 M 문제들은 모두 재귀함수로 풀 수 있으니 풀어보며 이해해보자!