재귀라는 용어는 그 자체로 무언가를 정의하는 프로세스로 정의될 수 있습니다. 간단히 말해서 함수가 직접 또는 간접적으로 자신을 호출하는 프로세스입니다.
재귀 사용의 장점
- 복잡한 함수는 재귀를 활용하여 더 작은 하위 문제로 나눌 수 있습니다.
- 중첩된 반복을 활용하는 것보다 재귀를 통해 시퀀스 생성이 더 간단합니다.
- 재귀 함수는 코드를 간단하고 효과적으로 보이게 만듭니다.
재귀 사용의 단점
- 재귀 호출을 통해 많은 메모리와 시간이 소비되므로 사용 비용이 많이 듭니다.
- 재귀 함수는 디버그하기가 어렵습니다.
- 재귀 뒤에 있는 추론은 때때로 생각하기 어려울 수 있습니다.
통사론:
def func(): <-- | | (recursive call) | func() ---->
예시 1: 피보나치 수열은 0, 1, 1, 2, 3, 5, 8…의 정수 수열입니다.
파이썬3
# Program to print the fibonacci series upto n_terms> # Recursive function> def> recursive_fibonacci(n):> >if> n <>=> 1>:> >return> n> >else>:> >return>(recursive_fibonacci(n>->1>)>+> recursive_fibonacci(n>->2>))> n_terms>=> 10> # check if the number of terms is valid> if> n_terms <>=> 0>:> >print>(>'Invalid input ! Please input a positive value'>)> else>:> >print>(>'Fibonacci series:'>)> for> i>in> range>(n_terms):> >print>(recursive_fibonacci(i))> |
MB에서 GB로
>
>산출
Fibonacci series: 0 1 1 2 3 5 8 13 21 34>
예시 2: 6의 계승은 6으로 표시됩니다! = 1*2*3*4*5*6 = 720.
파이썬3
Java를 배열로 나열
# Program to print factorial of a number> # recursively.> # Recursive function> def> recursive_factorial(n):> >if> n>=>=> 1>:> >return> n> >else>:> >return> n>*> recursive_factorial(n>->1>)> # user input> num>=> 6> # check if the input is valid or not> if> num <>0>:> >print>(>'Invalid input ! Please enter a positive number.'>)> elif> num>=>=> 0>:> >print>(>'Factorial of number 0 is 1'>)> else>:> >print>(>'Factorial of number'>, num,>'='>, recursive_factorial(num))> |
>
>산출
Factorial of number 6 = 720>
꼬리 재귀란 무엇입니까?
함수의 마지막 프로시저가 재귀 호출인 독특한 유형의 재귀입니다. 새로운 스택 프레임을 생성하는 대신 현재 스택 프레임에서 요청을 수행하고 출력을 반환함으로써 재귀를 자동화할 수 있습니다. 꼬리 재귀는 컴파일러에 의해 최적화될 수 있으므로 꼬리가 아닌 재귀 함수보다 더 좋습니다.
꼬리가 아닌 재귀 함수 대신 꼬리 재귀 함수를 사용하여 프로그램을 최적화할 수 있습니까?
n의 계승을 계산하기 위해 아래 주어진 함수를 고려하면, 이 함수는 처음에는 꼬리 재귀처럼 보이지만 비꼬리 재귀 함수라는 것을 알 수 있습니다. 자세히 관찰해보면 Recur_facto(n-1)가 반환한 값이 Recur_facto(n)에서 사용된다는 것을 알 수 있습니다. 따라서 Recur_facto(n-1)에 대한 호출은 Recur_facto(n)가 수행한 마지막 작업이 아닙니다.
파이썬3
문자열.형식 자바
# Program to calculate factorial of a number> # using a Non-Tail-Recursive function.> # non-tail recursive function> def> Recur_facto(n):> > >if> (n>=>=> 0>):> >return> 1> > >return> n>*> Recur_facto(n>->1>)> > # print the result> print>(Recur_facto(>6>))> |
>
>산출
720>
주어진 함수 Recur_facto를 꼬리 재귀 함수로 작성할 수 있습니다. 아이디어는 하나 이상의 인수를 사용하고 두 번째 인수에서는 계승 값을 수용하는 것입니다. n이 0에 도달하면 원하는 숫자의 계승값의 최종 값을 반환합니다.
파이썬3
스타 패턴 인쇄
# Program to calculate factorial of a number> # using a Tail-Recursive function.> # A tail recursive function> def> Recur_facto(n, a>=> 1>):> > >if> (n>=>=> 0>):> >return> a> > >return> Recur_facto(n>-> 1>, n>*> a)> > # print the result> print>(Recur_facto(>6>))> |
>
>산출
720>