Recursion

앞서 몇 포스트에서 재귀와 관련된 고찰과 관련된 내용들을 스크랩 하여 게시한 적이 있다.

재귀적 사고방식이 아직 익숙치 않아 베이직한 문제에도 머리를 뜯으며 강의와 간단한 문제풀이를 조금씩 진행하던 도중 수학적 귀납법 으로 접근하는 데에 좋은 문제를 발견하게 되어 정리해본다.

재귀의 기초

머릿글에서도 언급했듯 이번 재귀 사고방식을 연습하기 위해 인프런의 무료 강의를 수강하던 중 가장 뇌리에 깊게 박힌 사고방식은 수학적 귀납법 이다.

물론 재귀 설게를 위한 조건들 역시 기본적이면서도 직접 재귀 알고리즘 작성시(자주 작성할 일이 없었지만) 놓치는 것 들이라 목록화 하여 정리한 것도 상당히 좋았다.

재귀함수 를 귀납적 으로 접근하기 위해 반드시 Base Case 와 n-1까지 성립 가정 을 기억하자!

1. Recursion에서 적어도 하나의 Base Case(recursion 호출이 아닌 탈출 조건)이 존재해야 한다.


2. recursion case를 수행하다가 보면 결국 Base Case에 수렴해야 한다.


3. 재귀 함수는 자기 자신을 호출하는 것이 아닌 자기 자신과 똑같은 메서드를 호출 하는 것으로 이해하는 편이 더 좋다.

덧붙여 암시적 매개변수를 명시적 매개변수로 표현 하는 접근법은 재귀 설계를 위해 반드시 고려해야할 부분으로써 상당히 도움이 많이 되었다.

이는 실제 함수형 프로그래밍(선언형)에서도 중요한 포인트인데, 함수형 프로그래밍에서는 loop 보다는 Recursion을 이용해 반복 구문을 처리하는 경우가 많기 때문이라고 한다.

간단하게 start, end 인덱스를 매개변수로 명시해주는 것을 예로 들 수 있다.

수학적 귀납법

우선 countCells 문제를 접하기 전에 수학적 귀납법이 무엇인지 예시를 통해 아주 간단하게 살피고 가보자.

모든 자연수가 어떤 성질을 만족시킨다는 명제에 대한 수학적 귀납법을 통한 증명은 다음과 같은 두 단계로 구성된다.

1. 처음 오는 자연수(0 또는 1)에 대한 증명


2. n을 만족시킨다는 가정 하에 n+1 에 대한 증명


ex) 홀수의 합 공식 성립을 수학적 귀납법으로 증명
1 + 3 + 5 + 7 + . . . + 2n-1 = n^2
이 성립한다는 사실을 다음과 같이 증명할 수 있다.


1에 대하여 성립
  - 1에 대한 공식 1 = 1^2 는 자명하다.

n에 대하여 성립한다는 가정 아래 n+1에 대하여 성립
  - n이 성립하므로 다음이 성립한다.
    - 1 + 3 + 5 + 7 + . . .  + (2n-1) = n^2
    - 양변에 2n+1을 더하면 다음과 같다.
    - 1 + 3 + 5 + 7 + . . . + (2n-1) + (2n+1) = (n^2 + 2n + 1) => (n+1)^2
    - 이에 따라 n+1에 대하여 성립한다.

위의 내용에서 중요한(내가 생각했을 때) 키워드는 가정한다 이다.

즉, f(n-1)의 결과가 기대값과 일치한다는 가정 하에 f(n) = f(n-1) + (2n-1) 을 만족하는가?

그렇다면 결국 귀납법이 성립된다.

상당히 간단(?)하지만 심오(?)한 홀수 합에 대한 수학적 귀납법 증명이다.

위와 마찬가지로 재귀 역시 일반 코드의 해석(for, while과 같은 프로세스 추적)과는 조금 다른 접근 방식이 필요하다.

단순한 팩토리얼을 수학적 귀납법과 유사한 접근으로 풀어냈다.

먼저 앞서 factorial(n-1)이 옳다고 가정 함을 유의하자. 즉, n보다 작은 값 들을 모두 곱한 값들의 결과가 옳게 나온다’면’ 그 값에 n을 곱한 값이 n!이다

정리 : factorial(int n)은 음이 아닌 자연수 n에 대해서 1에서 n 까지의 곱을 올바로 계산한다.

증명

1. n <= 0 인 경우 1을 반환, 올바르다.

2. 자연수 k에 대해서 n<k인 경우 0에서 n까지의 곱을 올바르게 반환한다고 가정

3. n == k인 경우를 생각해보자 factorial(k)은 먼저 factorial(k-1)을 호출하는데 (2)번의 가정에 의해서 0 ~ k-1까지의 곱이 올바로 계산되어 반환된다.
메서드 factorial()은 그 값에 n을 곱하여 반환한다.
따라서 factorlai은 0 ~ k까지의 곱을 올바로 계산하여 반환한다.

역변환 문자열 출력 역시 재귀로 해결이 가능하다.

더 작고 간단한 문제로 나누어서 해결 하는 접근에 유의.

countCells

재귀를 이용한 간단한 grid 탐색 알고리즘에 위에 설명한 내용들 (작은 문제로 나누어 해결, 수학적 귀납법 접근) 즉, 간단한 재귀적 사고에 대해 잘 나타난 문제가 있다.

좌표를 이동해서 호출(이웃 좌표가 속한 blob의 크기를 구한다.) 및 이웃 좌표가 속한 blob의 크기를 구한 후 자신의 count를 더하여 프로세스를 진행하는 과정이 앞서 계속 설명했던 수학적 귀납법 및 재귀적 사고 접근 방식과 동일하다.

물론 위와 같이 간단하게 풀리는 문제만 있지는 않겠지만 절차적으로 프로세스를 따라가는 방식(머리로 CPU 돌리는 방식) 보다는 좀 더 재귀를 활용하는 데 연습이 될 것 이다.

참고 및 출처

https://blog.fupfin.com/?p=150