[Kotlin] Algorithm - Recursive
Kotlin2023-10-16 19:57 (KST)
Recursive
to refer to oneself when defining something
It is similar to Matryoshka, a traditional Russian doll (when you open a large doll, a small doll appears inside, and it continues until you can no longer hold it).
Recursion Algorithm
How to disperse operations while breaking down problems into smaller ones
Recursive Call
How to invoke yourself within an algorithm
Recursive Function
Functions that call themselves within the function and repeat logic within the function
Readability and reusability can be improved by replacing repeating statements (for and while).
Rule
Simplifies the problem.
- Define input and output values.
Divide the problem.
- Recursion calls should be made for smaller values within the same problem, i.e., subproblems.
- Break the problem down to a smaller problem based on the input value.
Define a Base Case.
- Repeat until the simplest problem (termination condition) is reached, which is no longer repeated (decomposed).
- If the termination condition is not specified, it falls into an infinite loop.
fun recursiveFunction(input: InputType): ReturnType {
// Base Case
if (Input is No longer able to decompose) {
return The result of solving the simplest problem
}
// Break it down into smaller problems and recall
val smallerInput = the process of breaking down into smaller problems
val result = recursiveFunction(smallerInput)
// Processing Results
// ...
return result
}
Limit
As recursive calls pile up, too much space is allocated to the stack memory area, resulting in Stack Overflow.
- Python: Recursion maximum depth allowed up to 1,000.
- JAVA: It varies depending on code and the amount of virtual memory allocated to the stack, but allows up to about 10,000.
![recursion.jpg](https://file.dico.me/2023/10/20231010101136_000.jpg)
Representative problem
Fibonacci numbers
- The first and second terms are always 1, and all subsequent terms are the sum of the preceding two terms.
- nth Fibonacci number = f(n) = f(n-1) + f(n-2)
fun main() {
println(fibonacci(1)) // 1
println(fibonacci(2)) // 1
println(fibonacci(3)) // 2
println(fibonacci(4)) // 3
println(fibonacci(5)) // 5
println(fibonacci(6)) // 8
}
fun fibonacci(n: Int): Int {
if (n <= 2) return 1
return fibonacci(n - 1) + fibonacci(n - 2)
}
Factorial
- the product of all positive integers less than or equal to the number
- When n is one natural number, the product of all natural numbers from 1 to n
- n! = n × (n-1) × (n-2) × ... × 1
fun main() {
println(factorial(1)) // 1
println(factorial(2)) // 2
println(factorial(3)) // 6
println(factorial(4)) // 24
println(factorial(5)) // 120
println(factorial(6)) // 720
}
fun factorial(n: Int): Int {
if (n <= 1) return 1
return n * factorial(n - 1)
}
Reference
https://ko.khanacademy.org/computing/computer-science/algorithms/recursive-algorithms/a/recursion
https://sattlub123.medium.com/함수형-프로그래밍-재귀-함수-recursive-function-f5bf74fd280d
https://velog.io/@geesuee/자료구조와-알고리즘-재귀-zix72gv8
https://ko.khanacademy.org/computing/computer-science/algorithms/recursive-algorithms/a/properties-of-recursive-algorithms
https://about-tech.tistory.com/entry/Algorithm-재귀-알고리즘이란-recursion-algorithm
https://velog.io/@anjaekk/알고리즘-재귀함수Recursive-Function
https://velog.io/@kai6666/알고리즘-재귀-함수-Recursion
https://brunch.co.kr/@newnorm/129