목차
1. 재귀함수란?
2. 스택 간단하게 알아보기
3. 재귀함수 예제
- 팩토리얼, 피보나치수열, 하노이의 탑
- 재귀함수 정의
- 재귀함수 실행순서
4. 재귀문제를 푸는 가장 좋은 방법?
재귀함수란?
재귀(recursion는 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다
재귀함수란? 함수를 정의할 그 함수 자신을 포함해서 정의하는 것이다.
▶ 재귀함수의 특징
- 재귀함수는 for문으로 대체할 수 있지만,
반복적 구조를 깔끔하게 쓰기위해서 특정상황에 사용한다.
- 하지만 for문이 더 복잡도가 낮고, 효율적일때가 많다.
- 재귀호출을 무한 반복하므로 종료조건이 필요하다.
- 선언적인 프로그램이다.
코드가 간결하고 이해하기 쉬울 때 사용.
스택
재귀함수를 이해하려면 스택을 알아야한다.
"나중에 들어온 데이터가 먼저 나간다."
마지막에 호출된 것이 먼저 종료되고, 이후 가장 위에있는 호출, 또 그 다음으로 위에있는 호출이 수행되며 넘어간다.
스택은 스택할 수 있는 최대 경계를 넘어가면 스택 오버플로우(Stack Overflow)가 일어난다.
재귀함수 예제
재귀함수 예제로는 팩토리얼, 피보나치수열, 하노이의 탑이 있다.
재귀함수를 정의하는 것과,
실행순서를 보면서 재귀함수가 어떻게 돌아가는지 알아보자..
▼팩토리얼
팩토리얼은 하나의 수에서 그 수와 같거나 작은 모든 정수의 곱이다.
ex) 5! = 5 * 4 * 3 * 2 * 1
팩토리얼을 재귀함수로 구현하면 다음과 같다.
▼재귀함수 정의
1. else:문
들어온 값과 바로아래의 값을 곱을 선언한다.
ex) 5 * 4, 4 * 3
2. if: 문
1이 들어왔을땐 1을 반환하며 종료한다.
▼실행 순서
num = 5
가 처음 들어가고 factorial(num-1)로 인해서 num은 4 -> 3 -> 2-> 1로 점점 스택이 쌓인다.
factorial(1)일 때, 1 리턴되며
factorial(2)상황으로 넘어간다.
그러면 2 * 1이 리턴,
결국 factorial(5) 처음 호출한 스택으로 넘어와서
factorial(5) = 5 * (4 * ( 3 * ( 2 * 1) ) )
위와 같은 형태가 된다.
▼ 피보나치 수열
피보나치 수열은 다음과 같이 정의된다.
f(0) = 0 , f(1) = 1
f(n) = f(n-1) + f(n-2) (n >= 2)
피보나치수열은 정의가 나와있는대로 그대로 정의해주면 된다.
▼재귀함수 정의
1. if num == 0:
return 0
f(0) = 0 을 표현한 것이다.
2. elif num == 1:
return 1
f(1) = 1 을 표현한 것이다.
3. elif num >= 2:
num = fibo(num-1) + fibo(num-2)
return num
n >= 2 의 조건
f(n) = f(n-1) + f(n-2) 를 표현하였고
return num으로 값을 리턴시키며 마무리되었다.
▼실행 순서
num = 0 -> 0
num = 1 -> 1
num = 2, fibo(2)
num = fibo(1) + fibo(0) = 1 + 0
num = 3 , fibo(3)
num = fibo(2) + fibo(1) = 1 + 1
num = 4, fibo(4)
num = fibo(3) + fibo(2) = 2 + 1
num = 5, fibo(5)
num = fibo(4) + fibo(3) = 3 + 2
num = 6, fibo(6)
num = fibo(5) + fibo(4) = 5 + 3
결과는 다음과 같다.
▼fibo(2) ▼fibo(3) ▼fobo(4) ▼fibo(5) ▼fibo(6)
fibo(6) = ( ( ( ( ( fibo(1) + fibo(0) ) + fibo(1) ) + fibo(2) ) + fibo(3) ) + fibo(4) )
▼ 하노이의 탑
하노이의 탑은 한 곳에 모여있는 원판을 반대쪽 기둥으로 옮기는 것이다.
큰 원판은 작은 원판위로 올라가면 안된다.
▼ 직접 하노이의 탑을 해봤을 때, 알게되는 규칙이 있다.
총 옮기는 원판의 개수가 n이라고 하면,
가장 큰 원판을 옮기기 전에,
마지막 기둥과 연결되는 기둥에 n-1개의 탑이 세워진다는 것.
그래서 우리는 n-1개의 원판을 연결 기둥에 모두 옮기고,
마지막 큰 원판 1개를 반대쪽으로 옮기면 된다.
n-1개의 원판들도 똑같이
n-2의 원판을 n-1개의 탑을 세우려는 곳과 다른 기둥에 세워야 옮길 수 있다.
이것이 반복되어 1개의 원판일때까지 올라간다.
▼재귀함수 정의
num = 옮겨야할 원판개수
start = 1번기둥 bridge = 2번기둥 end = 3번기둥
1. if num == 1:
원판이 하나남았을 때 시작지점에서 끝지점으로 원판을 옮긴다.
2. else:
2-1. hanoi(num-1, start, bridge, end)
num-1개의 탑을 전부 브릿지로 옮긴다.
2-2. hanoi(num-1, bridge, end, start)
num-1개의 탑을 전부 브릿지에서 끝지점까지 옮긴다.
프린트문을 통해서 원판의 이동을 나타낸다.
이렇게 정의해주면 된다.
▼ 실행 순서
hanoi(5, 1, 3, 2)일 때,
hanoi(num-1, start, bridge, end) 첫번째 재귀문
뜻 : n-1개의 탑을 연결기둥으로 옮긴다.!
먼저 1개가 end로 이동한다.
- > 2개의 탑이 bridge에 세워짐
- > 3개의 탑이 end에 세워짐
- > 4개의 탑이 bridge에 세워짐
- > 가장 큰 원판이 end로 이동
hanoi(num-1, bridge, end, start) 두번째 재귀
뜻 : 4개의 탑이 쌓여져있는 bridge에서 end로 탑을 다 이동시킨다.!
먼저 맨 위의 한개가 start로 이동
- > 2개의 탑이 end로 이동
- > 3개의 탑이 start로 이동
- > 4개의 탑이 end로 이동하며 end기둥에 5개의 탑이 세워지게 된다.
재귀문제를 푸는 가장 좋은 방법??
재귀함수를 잘 사용하는 가장 좋은 방법은,, 재귀적으로 생각하지 않는것이라고 한다..!
재귀함수를 잘 사용하려면 수많~은 재귀의 실행순서를 머릿속으로 큰그림을 그리려하면 안되고,
함수에서 중요한 요소들에 초점을 맞춰서 어떻게 구현할지 문제를 풀어나가라고 한다.
모두 나름의 방법으로 재귀함수를 잘 풀어내셨으면 좋겠습니다.........
다른 문제를 봐도 척척 풀어낼 수 있을지...
'Python' 카테고리의 다른 글
| [Python] 람다식 ( Lambda Expressions ) (2) | 2024.12.13 |
|---|---|
| [Python] 함수 global키워드, 가변 매개변수(args, kwargs) (2) | 2024.12.09 |
| [Python] 함수 def (2) | 2024.12.09 |
| [Python] while문 for문(리스트내포, 딕셔너리, 리스트 , 이중for문) (2) | 2024.12.06 |
| [Python] if문, elif문, else문, 중첩조건문 (0) | 2024.12.02 |
