순환의 개념과 기본 예제 1

수도(pseudo) 코드로 적음

자기 자신을 호출하는 함수

def func ():

print("Hello") //Hello가 무한히 출력된다.

func()

무한 루프에 빠지지 않기 위해서 recursion (재귀)를 벗어나는 base 조건이 필요하다

k=4

def func(k):

if k<0: return

else : 

print("Hello")

func(k-1)

Hello가 4번 출력되고 끝난다.  func(4),func(3),func(2),func(1)을 지나면서 Hello가 출력되고 func(0)이 호출되면 return되면서 func(0),func(1)...func(4)가 종료된다. 

Base Case: k<0이라는 조건처럼 재귀함수를 호출하지 않고 끝나는 문장이 필요하다.

Recursive Case: func(k-1)처럼 재귀함수를 호출하는 부분이 필요하다. 이 부분을 호출할수록 Base case에 도달해야 한다.

재귀함수로 1부터 n까지의 합을 구할 수 있다.

n=4

def func(n):

if n==0: return 0

else: return n+func(n-1)

print(def)

return 4+func(3)

 return 3+func(2)

  return 2+func(1)

   return 1+func(0)

               return 0

이렇게 흘러 가므로 재귀 호출이 끝나는 시점인 return 0부터 시작해서 0+1+2+3+4 = 10, 10이 출력된다.

팩토리얼

0!=1

n!=n*(n-1)!

def fac(n):

if n<2:return 1

else: return n*fac(n-1)

base case인 return 1이 될 때까지 fac(n-1)이 호출된다. return 1이 되면 차례로 1*2*3*...(n-1)*n이 계산된다.

제곱 계산

x^0=1

x^n = x*(x^(n-1))

def pow(x,n):

if n==0: return 1

else: return x*pow(n-1)

x*...x*1 여기서 x가 n번 곱해진다.

피보나치 수

f0=0

f1=1

fn = f_n-1 + f_n-2 if n>2

def fibo(n):

if n<2:return n

else : return fibo(n-1) + fibo(n-2)

유클리드 호제법으로 최대 공약수 구하기

두 수중에 큰수가 m 작은 수가 n이 된다. m 나누기 n 계산해서 n을 다시 m으로, 나머지를 n으로 해서 함수를 호출한다.

def gcd(m,n):

if m<n: m,n = n,m //m,n, swap

if m%n==0: return n

else: return gcd(n, m%n)

최소 공배수 구하기

lcm = (a*b)/gcd

출처 https://www.inflearn.com/course-status-2/