python 재귀함수

#함수(function)

#재귀 함수(recursion function)

- 자기 자신을 호출하는 함수

- 반복(loop)과 동일

- 하향식 설계

- while, for는 상향식 설계(동적계획법)

#꼬리 재귀 함수(tail recursion function)

- 자기 자신을 호출하는 함수

- 상향식 설계

#재귀함수로 1부터 n까지의 합 구해보기

def nth(n):

    if n>0:

        return n + nth(n-1)

    else:

        return 0

* n=5 // 1부터 5까지의 합을 구해보자.

# nth 함수에 매개변수로 5를 넘겨준다.

1. if 5>0:

return 5 + nth(4)

* return 5가 실행하기 전에 nth(4)가 먼저 실행, return 5는 남아있음

2. if 4>0:

return 4 + nth(3)

* return 4가 실행하기 전에 nth(3)가 먼저 실행, return 4는 남아있음

...

if 0>0:

return 0 + nth(-1)

* if 조건식이 성립하지 않기 때문에 명령이 실행되지 않고 else로 넘어감

else:

return 0

* else에서 0을 return한게 nth(1)로 넘어감... 여기서 부터 위로 올라간다.

if 1>0:

return 1 + 0

if 2>0:

return 2 + 1

if 3>0:

return 3 + 3

if 4>0:

return 4 + 6

if 5>0:

return 5 + 10

#따라서, 최종적으로 return 되는 값은 15이다.

#꼬리재귀 함수로 구할때는 따로 내려가고 다시 올라가는 과정없이 함수내에서 계산을 하며 함수를 호출하면 된다.

#알고리즘 복잡도

0(n)

- 이 알고리즘은 0이 n번안에 끝난다.

- 재귀함수의 한계는 1000번.. 1000번이상은 호출되지 않는다.

0(logn)

- 효율성이 뛰어남

0(n^2), 0(n^n)

- 효율성이 떨어짐..지수