재귀 호출(recursive call)
재귀 호출
- 함수 안에서 동일한 함수를 호출하는 형태이다
- 여러 알고리즘, 고급 정렬 알고리즘 작성 시 사용한다'
- 재귀 호출의 규칙
재귀 함수는 함수 안에서 자신을 호출해 반복 동작을 하는 함수로, 언제 반복을 탈출하는지의 대한 조건을 정해주는 것이 중요하다. 위를 보면 재귀 호출의 규칙으로 팩토리얼을 예로 작성한 것이다. 그것을 바탕으로 return이 되었을 때, 나오는 형식을 밑에 작성한 것이다.
- 재귀 호출 확인하기
위 함수는 팩토리얼을 생성한 것인데, 이걸로 확인해 볼 것이다. 2!, 3!, 4! 세 가지를 확인해 보자.
세 가지 모두 정확한 값을 출력했다. 2! 이면 반환값으로 2 * 함수(1)를 가져온다.
3! 은 반환값으로 3 * 함수(2)를 가져오기에 3 * 2 * 1 = 6이 나오게 된다.
4! 도 마찬가지로 4 * 함수(3)을 가져오기에 다시 함수 안으로 들어가서 4 * 3 * 함수(2)가 되고, 결과는 4 * 3 * 2 *1 = 24가 나오게 된다.
- 재귀 호출의 대해
- 재귀 함수는 내부적으로 스택처럼 관리가 된다. 스택처럼 관리가 된다는 것은 쌓인다는 것이다. 재귀 함수를 보면 반환값으로 자신을 호출하기 때문에 함수의 리턴값을 계속 타고 들어간다. 팩토리얼에서도 4! 을 생각해 보면 4 * 함수(3) -> 3 * 함수(2) 이런 식으로 진행되는데 그러면 맨 처음 값 4는 스택처럼 쌓이게 되고 마지막 함수가 끝날 때 다시 돌아가는 것이다.
값을 구해주기 위해 맨위에 있는 1부터 꺼내서 1 * 2 * 3 * 4 = 24가 되는 것이다.
말로 이해하기 어려우면 파이썬 코드분석 툴을 확인하면 편하다. ( https://pythontutor.com/ )
- 문제 풀이
첫 글자, 마지막 글자를 확인하고 다시 자신을 호출할 때, 슬라이싱을 사용하여 범위를 양쪽에서 한 글자씩 줄이면서 확인한다. 만약 글자의 개수가 홀수이면 마지막에 한 개가 남으면 회문이기 때문에 True를 반환하게 만들었다.
재귀 함수를 사용하기에 반복문을 사용하지 않고, if 문을 사용하여 조건을 걸어준다. 맨 처음 우리는 num 값이 1이 되면 종료해야 하기에 반환값을 '끝'으로 주고, 다음 조건에서 2로 나눴을 때 0(짝수), 그 외(홀수)를 나눠서 문제의 조건에 나온 계산식을 넣어주면 된다.
결과 값도 깔끔하게 나왔다.
- 참고
파이썬에서 재귀의 최대 깊이는 기본적으로 1000회로 설정되어 있다. 하지만 문제를 풀다보면 그보다 더 많이 사용해야 할 때도 있을 것인데, 그때 위 문장을 기억해서 활용하자. 재귀의 깊이를 () 안에 조건으로 설정할 수 있다.