#재귀

재귀적으로 푼다? 부분 문제에 대한 해법으로부터 만들어진다. 문제가 아주 작은 단위의 방식의 반복으로 풀린다면 재귀적으로 풀어보는 것을 시도해볼 수 있다. 문제를 푸는 방식에는 크게 상향식 재귀와 하향식 재귀가 있다.

상향식 재귀 방식 - base case, recursive case로 나뉘어서 푸는 방식이 이에 해당한다. 가장 기본적으로 생각할 수 있는 재귀 문제에 해당한다.

하향식 재귀 방식 - 본 문제를 어떻게 부분문제로 나눌 수 있는지 고민하는 방식이 이에 해당한다.

ex) n개의 계단을 오를 때, 한 사람이 1계단, 2계단, 3계단 오를 수 있다고 하자. n개의 계단을 오를 때 몇 가지의 방법이 있는지 구해주는 함수 만들기. 

이 문제의 경우 하향식 재귀 방식에 해당하는데, n개의 계단을 오르는 방법을 생각할 때 - 1계단 밑에서 올라오는 방식, 2계단 밑에서 올라오는 방식 2계단을 올라 n계단에 도착하는 방식, 마찬가지 방식으로 3계단 밑에서 3계단을 뛰어 올라오는 방식 - 세 가지가 있다. 

def building_runup(n):
	
    if n < 4:
    	return n
    else:
    	return building_runup(n-1) + building_runup(n-2) + building_runup(n-3)

 

ex) X,Y그리드 왼쪽 상단 꼭지점에 로봇이 놓여있다. 이 로봇이 오른쪽 혹은 아래쪽으로만 이동가능하다고 할 때, (0,0)에서 (X,Y)로 이동하는 경로를 구하기.

def building_runup(n):
	
    if n < 4:
    	return n
    else:
    	return building_runup(n-1) + building_runup(n-2) + building_runup(n-3)

building_runup(5) #11

다만, 재귀식으로 문제를 풀 때에는 공간 효율성이 나빠질 수 있음을 고려해야 한다. 재귀 호출이 한 번 발생할 때마다 stack에 새로운 계층이 생긴다. 이는 함수가 호출될 때, 함수가 끝나고 돌아갈 부분을 기억해놓는 것을 뜻한다. 재귀적으로 특정함수를 반복해서 호출한다면, stack이 많이 쌓이게 되고, 이는 결국 recursion error라는 에러문이 뜨게 된다. 한편, n번의 재귀호출로 문제를 풀어나갈 경우 O(n)만큼의 메모리 비용이 발생한다. 

반복문(for)으로 코드 작성할 때보다 훨신 효율적으로 짧게 코드를 작성하고자 할 때, 재귀함수를 쓰는 게 유용하다고 한다. 다만, 적정 수준에서 call stack을 감당할 수 있을 때 재귀를 쓰자.