1. Recursion (재귀)

재귀 함수란 함수 안에서 자기 자신(함수)를 호출하는 것을 말한다.

예를 들어보자. 다음의 예시에 sayHello 라는 함수가 있다.

def sayHello(n):
    if n == 0:
    	print("Bye!")
    else:
        print("Hello! " + str(n))
        sayHello(n-1)
	

다음의 함수의 인자로 n=3을 넣으면 결과는 다음과 같다.

sayHello(3)	

> Hello! 3
> Hello! 2
> Hello! 1
> Bye!

인자로 n=3을 받으면 다음과 같은 일이 일어난다:
n은 3, 즉 n==0이 false이므로 else문으로 간다. 그리고 Hello! 3을 출력한다.
sayHello(2)를 호출한다.

n은 2, 즉 n==0이 false이므로 else문으로 간다. 그리고 Hello! 2을 출력한다.
sayHello(1)를 호출한다.

n은 1, 즉 n==0이 false이므로 else문으로 간다. 그리고 Hello! 1을 출력한다.
sayHello(0)를 호출한다.

n은 0, 즉 n==0이 true이므로 if문으로 간다. 그리고 Bye!을 출력한다.

이렇게 이 함수는 자기 자신을 어떤 특정 조건 (if n==0)이 만족될때까지 호출을 하는 것이다. 이렇게 함수가 자기 자신을 호출하는 것을 재귀함수라고 한다.

2.Fibonacci (피보나치 수열)

피보나치 수열의 예를 들어 설명하면 더 쉽다.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, .....

앞의 두 숫자의 합이 뒤의 숫자가 되고 있다.
이것을 식으로 표현하면 다음과 같다.

f(n) = f(n-1) + f(n-2)

이렇다면, 피보나치 수열은 아까 설명한 재귀함수로 표현할 수 있다. 하지만 일단 일반 함수로 먼저 표현한 것을 보도록 하자.

2-1. 일반 함수로 표현

def fibonacci(n):
    a,b = 1,1
    if n==1 or n==2:
        return 1
        
    for i in range(1,n):
        a,b = b, a+b

    return a

2-2. 재귀 함수로 표현

def fibonacci(n):
    if n==1 or n==2:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

2-3. Lambda 로 표현

fibonacci = lambda n: 1 if n<=2 else fibonacci(n-1) + fibonacci(n-2)

2-4. Array를 이용해 표현

def fibonacci(n):
  if n < 0:
    ValueError("Input 0 or greater only!")

  fibs = [0, 1]
  
  if n <= len(fibs) - 1:
    return fibs[n]

  while n > len(fibs) - 1:
    fibs.append(fibs[-1] + fibs[-2])
    
  return fibs[-1]