Data Structures and Algorithms (6)

Data Structure and Algorithms (6)

1. 재귀용법 (Recursive Call, 재귀호출)

*고급정렬 알고리즘에서 사용됨

재귀 용법 (recursive call)

• 함수 안에서 동일한 함수 호출하는 형태
• 여러 알고리즘 작성시 사용되므로 익숙해져야함

ex) !: factorial

try

2! = 2 X 1
4! = 4 X 3 X 2 X 1 = 4 X 3!

규칙발견

n! = n x (n-1)!

code

def factorial (num):
if num>1:
  return num * factorial(num-1)
else:
   return num

*시간복잡도/공간복잡도 = O(n-1)이기 때문에 O(n)
*스택의 자료구조와 동일하게 움직임
*파이썬 : 재귀함수 호출 1000회 이하!

ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

2. 재귀용법을 활용한 프로그래밍 연습

1) 1부터 num까지의 곱 출력

반복문 (Loop)

def multiple(num):
result = 1
for index in range(1,num,+1)
  result = result * index
return result

재귀 (recursive call)

def multiple(num):
if num <= 1:
  return num
return num * multiple (num-1)

2) 숫자가 들어있는 리스트가 주어졌을 때 리스트의 합을 리턴하는 함수

import random
data = random.sample(range(100), 10)
ㅤ
def sum_list(data):
if len(data) <= 1;
  return data[0]
return data[0] + sum_list(data[1:])

3) 회문 (palindrome)

def palindrome(string):
 if len(strng) <= 1:
return True
ㅤ
if string[0] == string[-1]:
return palindrome(string[1:-1])
else:
return False

4) 정수 n에 대해
n 홀수 : 3 X n + 1
n 짝수 : n / 2
-> 결국 n이 1이 될때까지 과정 반복

def func(n):
if n <= 1 :
  return n
elif n % 2 == 1
  n = 3 X n + 1
  return func (n)
else:
  n = n/2
  return func(n)

5) 정수 4를 1,2,3의 조합으로 나타내는 방법 7가지
정수 n 주어졌을때 n을 1,2,3의 합으로 나타낼 수 있는 방법의 수

def func(data):
if data == 1:
  return 1
if data == 2:
  return 2
if data == 3:
  return 4
 ㅤ
return func(data-1) + func(data-2) + func(data-3)

본 게시글은 fastcampus 이준희강사 수업을 듣고 개인적으로 정리한 내용임을 밝힘.