Python[CS61A] Recursion: Videos 정리

Self_Reference 영상

def print_all(x):
    print(x)
    return print_all
    
print_all(1)(3)(5)

print_all 함수는 받은 인자를 프린트 해주고, 해당 함수를 다시 리턴해주는 셀프 리턴 함수입니다. 

print_all의 리턴문에는 ()가 없다는 점을 확인하실 수 있는데요. 즉, 함수를 반환하지만 호출하진 않는다는 거죠. 

 

따라서, print_all(1)(3)(5)는 무한히 작동되지 않고, 5를 프린트하고 나서 끝날겁니다.

 

이어서 다른 예시를 살펴보죠.

def print_sums(x):
    print(x)
    def next_sum(y):
        return print_sums(x+y)
    return next_sum
    
print_sums(1)(3)(5)

이번엔 함수 print_sums 안에, next_sum이란 함수를 정의하고 print_sums가 next_sum을 리턴하도록 코드를 짜보았습니다. print_sums(1)으로 인해서 x 인자에 1이 들어가고, 사용자에게 1이라는 값을 출력해줄겁니다. 그 후, next_sum 함수를 해당 로컬 프레임 f1에 정의하고, 이 next_sum 함수를 리턴하는데, (3)이 해당 함수를 호출합니다. 3을 y인자로 받고, print_sums를 리턴하고, (x+y)인자를 전달해서 해당 함수를 호출하네요. 여기서 y는 당연히 3일거고, x는 어디서 받는걸까요? x는 f1프레임에서 받아오니까, 1값을 받아올겁니다. 그렇게 새로운 인자 4가 새로운 print_sums로 전달될겁니다.

---

Recursive Functions 영상

 

Recursive function: A function that the body of that function calls itself, either directly or indirectly.

 

Digit Sums:

2 + 0 + 1 + 3 = 6

만약 a가 9로 나뉘어진다면, digit_sum(a)도 0로 나눠진다는 흥미로운 사실.

 

Sum digits without a while statement. while문을 사용 못하니까, recursion을 사용해볼겁니다.

 

Anatomy of a Recursive Function:

Recursive함수 구성은 크게 2가지로, base cases를 체크하는 구간과 recursive cases를 체크하는 구간으로 나뉩니다.

• base cases are evaluated without recursive calls (여기선 if n<10)
• recursive cases are evaluated with recursive calls 

def split(n):
    return n // 10, n % 10

def sum_sigits(n):
    if n < 10: #test for a base case
        return n
    else:
        all_but_last, last = split(n)
        return sum_digits(all_but_last) + last

---

Recursion in Environment Diagrams 영상

def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n-1)
            
fact(3)

해당 코드를 environment diagram으로 표현해보기:

나중에 첨부하자 너무 귀찮음

 

Iteration과 Recursion의 비교

def fact_iter(n):
    total, k = 1, 1
    while k <= n:
        total, k = total*k, k+1
    return total

---

Verifying Recursive Functions 영상

Recursive function의 로직을 점검하는 방법은 아래와 같습니다.

def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n-1)

 

fact함수가 올바르게 시행되는지에 대한 확인 절차:

1. base case 검증하기

2. fact 함수를 functional abstraction로 대하기. 이게 무슨 말이냐면:

Don't think about how it's implemented. Think about what it's supposed to do. 예를 들어, 해당 예시에선 fact(n-1)이 n-1의 팩토리얼을 리턴해야한다고만 받아들이기.

3. fact(n-1)이 올바르다고 가정. 올바르게 n-1의 팩토리얼을 리턴한다고 가정하는 것.

4.  fact(n-1)이 올바르다는 가정하에, fact(n)이 올바르게 시행됨을 검증

---

Mutual Recursion 영상

Mutual Recursion: Occurs when two different functions call eact other

 

Lun Algorithm: Used to verify credit card numbers

유효한 신용카드의 카드번호는 Luhn sum이 10의 배수가 되어야한다.

Double the value of every second digits.

8은 2배 되어 16이 되었지만, 9보다 큰 숫자라서 한 번 더 연산 시행

def split(n):
    return n // 10, n % 10

def sum_digits(n):
    if n < 10: #test for a base case
        return n
    else:
        all_but_last, last = split(n)
        return sum_digits(all_but_last) + last
        
def luhn_sum(n):
    if n < 10:
        return n
    else:
        all_but_last, last = split(n)
        return luhn_sum_double(all_but_last) + last
        
def luhn_sum_double(n):
    all_but_last, last = split(n)
    luhn_digit = sum_digits(2 * last)
    if n < 10:
        return luhn_digit
    else:
        return luhn_sum(all_but_last) + luhn_digit

 

---

Recursion and Iteration 영상