[💬] 코드몽키 벗어나기 - 8

여태까지의 요약.

1. 프로그래밍 언어를 파악하기 위해서는 언어가 어떤 데이터를 어떤 프로시저를 어떻게 사용하는지를 파악해야 한다.

2. 그러기 위해 가장 기본개념들을 먼저 파악하자.

-> 프리미티브 데이터, 프리미티브 프로시저, definition, conditional expression, 추상화 등등을 배움.

3. 다음으로는 추상화 할 때, 그 로컬 추성화, 글로벌 추상화 등을 배움.

지금부터 배워야 하는 내용은, 여태까지 배운 기본 개념들을 어떻게 이용하는가이다.

지금까지는 체스의 말의 종류에 대해 배웠다면, 지금부터는 체스의 전략을 배워야 한다.

그중에 하나가 Linear Recursion이다.

팩토리얼을 계산 하기 위해서는 아래와 같은 식을 풀어야 하는데,

재귀를 사용하면 이렇게 된다.

그림으로 나타내면

근데 재귀가 아니라 iteration 을 사용하면 이렇게 된다.

그림으로 나타내면

둘이 본질적으로 다른점은, 재귀의 경우는 중간계산을 계속 트랙킹 해줘야 하는데

iteration의 경우는 그럴필요가 없다는점. 메모리적으로 더 효과적이라는것이다.

또 하나의 계산 방법으로 Tree Recursion 이 있다.

예로 피보나치 수열을 보자.

각각의 숫자는 앞의 두 숫자의 합인 수열인데,

이것을 수식으로 나타내면 이렇고,

Lisp로 나타내면 이렇게 된다.

이걸 그림으로 나타내면 이렇게 되는데, 보면 알다시피 매우 비효율적이라는것을 알 수 있다.

계산 수가 인풋에 exponential grow 한다.

다르게 계산하는 방법으로는 이렇게 하면 된다.

이렇게 하나의 식을 계산할 때에도 여러가지 방법이 있고, 방법에 따라 리소스를 얼마나 사용하는가가 매우 다르다는것을 알 수 있다.

음... 뭐 대충 보면

어떠한 프로시저를 구현하기 위해서는 뭐 이러저러한 방법들이 있다.

linear recursion, tree recursion, iteration 등등등.

근데 그게 문제에 따라서 계산 리소스가 크게 차이가 난다. 이런 말이네. 뭐 기본적인 내용이구요

책 읽다가 tail recursion 꼬리 재귀라는 말이 나와서 찾아봤더니

이런 열띤 토론을 벌이시는 분들을 찾아냄.

글쿠나. 그렇군 하고 걍 슥 훑고 넘어감.

오늘은 여기까지.

댓글 3