[Python]재귀의 이해

재귀함수

: 스스로를 호출하는 함수

---

* django 개발할 때는 크게 할 필요는 없음

* 코딩테스트에서는 재귀함수를 모르면 손도 못대는 중요한!! 문제 유형들이 많음

 

return값이 없는 재귀함수

예시로 알아보자!

def recursion(n):
	if n < 5:
    	print(n) 
        recursion(n+1)
        
recursion(1)

# 1
# 2
# 3
# 4

 

return값이 있는 재귀함수

def recursion(n):
	if n <= 0:
		return 0
	return n + recursion(n-1)
    
print(recursion(4))

# 4+3+2+1
아래는 과정을 설명
# 4+r(4-1)+r(4-1-1)+r(4-1-1-1)
# 4+r(3)+r(2)+r(1)

아직 이해가 잘 안됨
n이 -1씩 되는건 알겠는데 왜 그게 이전n에 계속 더해지는지 모르겠음

---

재귀함수 작성법

재귀 문제 유형인지 구분하는 법!

: 재귀로 코드를 짤 수 있다는 걸 어떻게 알 수 있을까??

    1. 문제 푸는 전체 과정을 펼쳐 생각해보았을 때

    2. 문제풀이 과정의 일부분이 문제를 푸는 전체 과정과 유사함

문제 풀이 과정에서 비슷한 논리가 꼬리에 꼬리를 무는 형태로 이루어져 있음

---

연습문제1)

팩토리얼(!)은 어떤 수보다 작거나 같은 모든 양의 정수를 순차적으로 곱한 값을 의미
ex) 4 팩토리얼(4!) = 4x3x2x1
16 팩토리얼(16!)의 값을 구해보세요. (단, 0 팩토리얼은 1입니다.)

1. 재귀문제유형인지 구분하기

문제 푸는 과정을 풀어보면 16! = 16*15!,  15! = 15*14!, 14! = 14*13!, n! = n*(n-1)! 이런 식으로 진행 되는 문제!

= 16!을 구하는 과정 일부에 15! 14! ··· 1! 가 있는데 이는 문제를 푸는 전체 과정과 유사! 즉, 재귀문제 유형임을 알 수 있음

 

2. 종료조건 구하기

문제에 (단, 0 팩토리얼은 1입니다.) 부분을 종료조건으로 볼 수 있음

= n이 0또는 1이 되었을 때 종료하도록!

 

3. 문제 풀어보기

def factorial(n):
	if n <= 0 : #종료조건
    	return 1
    return n * factorial(n-1) #반복되는 식
    
print(factorial(16))

---

연습문제2)

피보나치 수열은 첫째 항이 0, 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열
ex) 첫째항0, 둘째항 1, 셋째항 1, 넷째항 2, 다섯째항 3, 여섯째항 5
1피보나치 수열의 12번째 항을 구해보세요.

1. 재귀문제유형인지 구분하기

문제 푸는 과정을 풀어보면 1+1=2, 1+2=3, (n-1)+(n-2)=n 이런 식으로 진행 되는 문제!인데,,

= 바로 앞 두 항을 더해 값을 내는 방식이 문제를 푸는 전체 과정과 유사! 즉, 재귀문제 유형임을 알 수 있음

 

2. 종료조건 구하기

문제에 (첫째 항이 0, 둘째 항이 1) 부분을 종료조건으로 볼 수 있음

= n이 0또는 1이 되었을 때 종료하도록!

 

3. 문제 풀어보기

def fibonacci(n):
	if n == 1: #종료조건
    	return 0
    elif n == 2: #종료조건
    	return 1
    return fibonacci(n-1)+fibonacci(n-2) #반복되는 식
    
print(fibonacci(12))

전혀 이해를 못했음.. 아니 왜 저게 피보나치 수열이지

---

연습문제3)(과제)

파스칼의 삼각형(Pascal's triangle)은 다음과 같이 만들어지는 삼각형을 의미
1. 첫번째 줄에는 1을 쓴다.
2. n 번째 줄 (n>=2)줄을 만들 때 n-1 번째 줄의 왼쪽 숫자와 오른쪽 숫자를 더한다.
    n-1 번째 줄의 왼쪽 숫자 혹은 오른쪽 숫자 중 하나가 없을 경우 존재하는 수만 더한다.
ex) 
                     1
                   1   1
                 1   2  1
               1   3   3  1
             1   4   6   4  1
          1   5  10  10  5  1
      1   6  15  20  15  6   1
파스칼의 삼각형 8번째 줄을 리스트로 출력하는 함수를 만들어보세요.

1. 재귀문제유형인지 구분하기

문제 푸는 과정을 풀어보면 0+1=1, 1+1=2, (a+b)*n 이런 식으로 진행 되는 문제!인데,,

= n-1 번째 줄의 왼쪽 숫자와 오른쪽 숫자를 더하는 방식이 문제를 푸는 전체 과정과 유사! 즉, 재귀문제 유형

 

2. 종료조건 구하기

문제에 (첫번째 줄에는 1을 쓴다.) 부분을 종료조건으로 볼 수 있음,,,,,???????????????

= n이 1이 되었을 때 종료하도록!

 

3. 문제 풀어보기

def pascal(n):
	if n == 1: #종료조건
    	return 1
    return pascal(n-1)+pascal(n-2) #반복되는 식
    
print(pascal(8))
while
break
1에서시작

count=n
while 1<count
	n-

재귀함수로 못바꿈

다시 고민해보기

 

 

 

재귀함수 작성시 유의할 점!

1. 모든 재귀함수는 반복문으로 구현이 가능하다!

    - 그럼 왜 재귀함수로 쓰는가? => 코드가 짧아지기 때문

    - 쓰다보면 재귀함수로 했을 때 더 효율적인 코드 작성이 가능하단 걸 알게 됨

 

2. 종료조건을 꼭 명시 해주어야 한다!

    - 코딩테스트에는 공간제약, 시간제약, 메모리제약이 있음 => 끝도없이 호출되는게 정답일 수 없음

    - 언제 멈추게할지 판단할 수 있어야 함

    - 위 return값이 없는 재귀함수에서 종료조건인 if문을 지웠을 경우 아래 에러가 발생한다

# error
RecursionError: maximum recursion depth exceeded while calling a Python object
# 재귀함수의 최대 dp가 끝났다는 뜻으로 종료조건을 제대로 안했다는 의미

    - 재귀함수 최대 호출 횟수 파악하는 방법

      최대 재귀 깊이 (maximum recursion depth)

      : 재귀함수를 최대로 호출할 수 있는 횟수 파악

        1000번 이상 찍히면 잘못된 재귀함수를 작성한 것임

print(sys.getrecursionlimit()) # 1000

 

 

 

 

 

추가 공부 필요

* bfs/dfs?

* 트리 순회(중위/전위/후위 순회)? 재귀로 구현함

 

클래스 심화32:33부터