재귀함수
재귀함수
- 반복의 또 다른형태
- 함수 안에 자기자신(함수)이 들어가 계속 반복되는 형태
EX) recursion 이라는 함수를 만들어 그 안에 또 recursion 함수를 넣어서 실행시켜보았습니다.
이런형태의 함수를 재귀함수라고 합니다.
그러면 print("recursion!")이 실행되면서 무한루프가 발생하게 됩니다.
(파이썬에서는 무한히 반복되지 않기위해서 한계를 설정해놓았기 때문에 아래 traceback이 뜨는 것을 확인해 볼 수 있습니다.)
루프를 보면 접근방법에 따라서 분류할 수 있습니다.
상향식 접근방법과 하향식 접근방법이 있습니다.
예시를 들어가며 설명하겠습니다. 1부터 5까지 출력하는 함수로 설명하겠습니다.
1. 상향식 접근
- 상향식 접근은 계산하면서 아래로 내려가는 형태를 말합니다.
1) 루프 (대표적으로 while)
- 1부터 5까지 while 루프를 사용해서 출력하는 형태를 만들어보았습니다.
- while루프는 1부터 차례대로 증가시키면서 출력하기 때문에 상향식 접근이라고 합니다.
결과창
2) 꼬리 재귀(tail recursion)
- 1부터 5까지 재귀함수를 사용해서 출력하는 코드를 만들어보게 되면 아래와 같은 형태가 나오게 됩니다.
- 재귀함수와 비슷한 형태이지만 출력형태가 while과 비슷하다는 것을 볼 수 있습니다.
- 이것을 풀어서 보게 되면 n자리에 5를 대입해서 풀어보았습니다.
- 먼저 보라색박스는 count(5,1), 파란색 박스는 count(5,2), 하늘색박스는 count(5,3), 초록색박스는 count(5,4),
노란색 박스는 count(5,5), 빨간색 박스는 count(5,6)을 의미합니다.
- count(5)가 실행되면 먼저 print(1)이 출력되고 그 이후에 count(4)가 실행됩니다. 그렇게 계속 실행되다 보면 빨간색 박스까지 실행되게 됩니다.
- count(5,6)은 조건에 맞지 않기때문에 실행되지 않습니다. 그러면서 빠져나오기때문에 함수가 끝나게 됩니다.
- 그래서 1,2,3,4,5가 출력되는 것을 볼 수 있습니다.
2. 하향식 접근
- 하향식 접근은 출력형태를 만들어놓고 회수하는 형태를 말합니다.
1) 재귀(recursion)
- 1부터 5까지 재귀함수를 사용해서 출력하는 코드를 만들어보게 되면 아래와 같은 형태가 나오게 됩니다.
- 이것을 풀어서 보게 되면 n자리에 5를 대입해서 풀어보았습니다.
- 먼저 보라색박스는 count(5), 파란색 박스는 count(4), 하늘색박스는 count(3), 초록색박스는 count(2),
노란색 박스는 count(1), 빨간색 박스는 count(0)을 의미합니다.
- count 함수안에 또 count 함수가 들어가는 형태를 볼 수 있습니다.
- 계속하게 들어가게 되면 if문으로 빨간색 박스가 성립하지 않기 때문에 빠져나오게 됩니다.
- 그러면 그 밑에 있는 print가 출력되면서 1,2,3,4,5가 출력되는 것을 볼 수 있습니다.
- 꼭 print함수가 회수하는 것의 형태로 보여 하향식 접근이라고 볼 수 있습니다.
