재귀 함수❗ ing

이은택·2021년 11월 13일

알고리즘

목록 보기

13/15

코드잇 재귀 함수 연습

1. 피보나치 수열

1차 실패

구상 45분

2차

구상 25분

구현 1분

# n번째 피보나치 수를 리턴
def fib(n):
    # 코드를 입력하세요.
    if n == -1:
        return 1
    elif n == 0:
        return 0
    else:
        return fib(n-2) + fib(n-1)
# 테스트: fib(1)부터 fib(10)까지 출력
for i in range(1, 11):
    print(fib(i))

오래 걸린 이유
- 재귀함수 미숙함, 힌트 X
- 팩토리얼을 재귀함수로 풀이할 경우 base case가 하나인데 (factorial(0) 일 경우 return 1 ) 피보나치 수열도 base case를 하나라고 무의식적으로 가정하고 풀이를 해서 구상하는데 문제가 발생

답안비교후 코드개선

n이 0과 -1 일 경우의 base case 값을 구하는게 아니라 n이 1과 2일 경우에 base case 값 1을 리턴하면 되는 거였다 ...ㅋ 이걸 왜 생각 못했지
base case 작성시 부등호를 사용해 두개의 base case 조건문을 하나로 간단히 작성이 가능하다.

2. 숫자 합

1차

구상 5분

구현 1분

# 1부터 n까지의 합을 리턴
def triangle_number(n):
    # 코드를 입력하세요
    if n == 1:
        return 1
    else:
        return triangle_number(n-1) + n

# 테스트: triangle_number(1)부터 triangle_number(10)까지 출력
for i in range(1, 11):
    print(triangle_number(i))

3. 자릿수 합

1차

구상 11분

구현 13분

# n의 각 자릿수의 합을 리턴
def sum_digits(n):
    # base
    if n < 10:  📌
        return n
	# recursive
    else:
        next_n = int(str(n)[:-1])
        return n % 10 + sum_digits(next_n)

# 테스트
print(sum_digits(22541))
print(sum_digits(92130))
print(sum_digits(12634))
print(sum_digits(704))
print(sum_digits(3755))

막힌부분

📌 base case 조건문을 부분을 if len(str(sum_digits)) == 1: 로 작성을 했는데 처음에는 len 과 str 함수사용시 오류같은 건가 해서 조건문을 if n < 10: 로 고쳐서 해결을 했는데 지금보니 인자값으로 n 대신에 재귀함수 sum_digit 을 넣어서 나온 에러였다... 왜 그랬을까? 희한한건 에러 결과가 ValueError: invalid literal for int() with base 10: '' 로 나온거였다. 잘못된 입력값과 이 에러가 나온 이유에대한 연결고리를 아직은 모르겠다.

Traceback (most recent call last):
  File "main.py", line 11, in <module>
    print(sum_digits(22541))
  File "main.py", line 8, in sum_digits
    return n % 10 + sum_digits(next_n)
  File "main.py", line 8, in sum_digits
    return n % 10 + sum_digits(next_n)
  File "main.py", line 8, in sum_digits
    return n % 10 + sum_digits(next_n)
  [Previous line repeated 1 more time]
  File "main.py", line 7, in sum_digits
    next_n = int(str(n)[:-1])
ValueError: invalid literal for int() with base 10: ''

답안비교후 개선사항

recursive case부분에서 int(str(n)[:-1]) 대신에 n // 10 도 활용이 가능하다는 생각을 하지 못했음
else 문을 쓰지 않고 return 을 바로 사용 하던데 코드 가독성 면에서 어떤게 더 나을까? 별차이 없고 개인 취향대로 쓰면 되는 것일까?

4. 리스트 뒤집기

1차

구상 6분
구현 5분
- 코드
```
# 파라미터 some_list를 거꾸로 뒤집는 함수
def flip(some_list):
    # 코드를 입력하세요.
    if len(some_list) == 1:
        return some_list
    return some_list[-1:] + flip(some_list[:-1]) # 📌
        

# 테스트
some_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
some_list = flip(some_list)
print(some_list)
```
- 막힌부분
  - 📌 some_list[-1:] 대신에 some_list[-1] 를 적어서 서로 다른 자료형인 정수와 리스트가 더해지는 코드를 작성 해서 생기는 에러 TypeError: unsupported operand type(s) for +: 'int' and 'li...가 발생 에러를 해결 하기 위해서 list(some_list[-1]) 을 적었는데 TypeError: 'int' object is not iterable 가 나옴 type(list[1]) 을 실험 삼아 쳐보니 list가 아닌 <class 'types.GenericAlias'> 가 나온다. 아무래도 list 라는 함수가 일반적인 리스트를 리턴해주는게 아닌 object 형식으로 반환 되다 보니 생기는 에러 인것 같다.

다른 방식 - pop() 사용

# 파라미터 some_list를 거꾸로 뒤집는 함수
def flip(a):
    # 코드를 입력하세요.
    if len(a) == 1:
        return a
    return [a.pop()] + flip(a)
        

# 테스트
some_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
x = flip(some_list)
print(x)
print(some_list)