📜 제목으로 보기

method 수준에서 반복문과 꼬리재귀
- 반복문 to 꼬리재귀
  - ex1) 피보나치 수열 반복문(업데이트 변수 2개)
  - ex2) 누적합 반복문(업데이트 변수 1개 + n도 로직에 사용)
- 꼬리재귀 to 반복문
  - ex1) 피보나치 수열 꼬리 재귀
  - ex) 누적합 꼬리 재귀

method 수준에서 반복문과 꼬리재귀

반복문 to 꼬리재귀

ex1) 피보나치 수열 반복문(업데이트 변수 2개)

피보나치 수열의 반복문 예시

def fibonacci_loop(n):
    assert n > 0, "0이하를 입력할 수 없습니다."
  
    if n <= 1:
        return n
  
    a, b = 0, 1  # 1 2  3 5
  
    for _ in range(2, n + 1):
        a, b = b, (a + b)
  
    return b

01 전체로직을 업데이트변수를 가지는 꼬리재귀 함수helper로 추출

반복문을 실행시키는 메서드 파라미터 n만 존재하는 상태이므로 전체로직을 꼬리재귀용 파라미터가 추가될 새 메서드(helper)로 추출한다.

02 반복문에서 업데이트되는 변수들의 초기값들의, 반복문 위의 초기값을 -> 파라미터로 추출 후 최초 호출 인자로 대입

반복문 위에 초기값으로 시작하여 업데이트 되는 변수(a,b)들을 파라미터로 빼고, 반복문 위 초기값(0,1)들을, 최초 호출시 인자로 사용하도록 올린다.
- 재귀함수는 업데이트되는 값들을 파라미터로 올리고 다음 재귀 호출시, 인자에서 업데이트 시키는데
  - n을 인자로 호출하여 시작해서 n-1로 업데이트되는 것처럼, 다른 파라미터도 초기값을 인자로 호출하여 매번 업데이트 시킨다.
    - 재귀함수는 n부터 시작해서 내려가므로, n이 초기값이다.
    - 꼬리 재귀함수는 n이외의 파라미터도 시작 초기값을 준다
- 업데이트 되는 필수 누적결과값 b의 파라미터 추출 및 초기값을 최초호출 인자로
- 업데이트 되는 변수 a의 파라미터 추출 및 초기값을 최초호출 인자로

03 return문에서 다음 꼬리재귀만 호출 + 업데이트 로직을 인자로 대입

꼬리재귀를 만들기 위해, return문에서 업데이트변수들을 품은 꼬리재귀를 호출하되, 업데이트 로직을 반영해서 호출하도록 한다.

04 반복문 끝 횟수(n to 시작)의 다음을 종착역으로 잡아, 종착역에서 누적 결과값 반환

꼬리재귀는 마지막 연산(n -> 2)의 다음을 종착역으로 잡고, 그 종착역에서 누적된 결과값을 반환한다
- 현재 반복문이 n부터 -1씩 업데이트되서 2까지 가고 있다.
- 2에서 누적연산이 끝나고, 다음번인 1을 종착역으로 잡아, 연산없이 누적된 결과값을 반환해줘야한다.

ex2) 누적합 반복문(업데이트 변수 1개 + n도 로직에 사용)

누적합 반복문으로 구현

def cumulative_sum_loop(n):
    s = 0
    for i in range(1, n + 1):
        s += i
    return s

6b089eca-d2b8-46db-99d8-f80c20c7401b

반복문에서 업데이트시 index i를 사용하지만, n번째라고 생각하고 업데이트 인자에 반영해준다.
- 반복문은 1부터 시작하지만, 재귀함수는 n부터 깍으면서 내려가며, n-1번째 연산시, index i는 n이다.

꼬리재귀 to 반복문

ex1) 피보나치 수열 꼬리 재귀

01 꼬리재귀문과 [꼬리재귀 호출부]를 복사해놓고 시작한다.

호출부의 인자는 원래 반복문 위에 있던 업데이트 변수들의 초기값들이다.

02 n부터 깍여내려가, early return되는 종착역을 보고, (1)연산하는 종착역인지 vs 누적결과값만 반환하는 특이점인지 확인 뒤, (2)업데이트 반복문 횟수(n~종착역직전 or n~종착역) 및 return할 누적결과값 변수를 확인후 일단 n만 인자로 가지는 메서드를 작성한다.

n부터 내려가다가, 종착역은 n==1이며, 연산없이 결과값만 반환하므로 실제 반복문 구간은 n==2까지다.
- 2~n까지 range(2, n+1)로 작성해준다.
  - 스샷에는 range(2, n)으로 오타

03 꼬리재귀 최초 호출부로 넘어간, 누적 업데이트 변수들의 초기값들을 확인하여, n을 제외하고 반복문위에 업데이트 변수의 초기값으로 선언한다.

e32d5aa3-7645-4927-9243-323e18f28450

04 n정의 파라미터들 -> n-1일때 업데이트되는 인자들을 보고, 업데이트 로직을 반복문 내부에 넣어준다.

python이므로, 파라미터 복사 = 인자 복사 형태로 그대로 복사해서 넣어줘도 된다.
만약, 업데이트로 로직에 n이 들어가면, 반복문의 index i 를 사용하면 된다.

1e9c1d3d-50df-4c7b-a3c4-a6a3c7530bdc

05 특이점 종착역을 포함하여 초기값 early return문들은 그대로 복사 한 뒤, 종착역의 누적결과값 반환이 아니라, 초기값들을 반환하도록 처리해준다. (특이점 종착역도 연산이 없어서 반복문에 반영안되므로 초기값으로서 early return으로 처리해줘야한다. 만약, 의미가 없는 초기값이면 삭제해도 된다.)

특이점 종착역은, 누적결과값만 반환하고 업데이트 연산로직이 없어서 반복문에 반영이 안됬다. -> 그 종착역과 그 이전 초기값들 처리를 해줘야한다.

ex) 누적합 꼬리 재귀

3eb9ba74-70eb-4ff8-8da6-87564ba9205c