[Kotlin] Algorithm - Recursive

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.

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

[Kotlin] Algorithm - Combination - Dico

알고리즘 조합을 kotlin으로 구현

dico.me

[Kotlin] Algorithms - Permutation - Dico

알고리즘 조합, 순열, 중복순혈을 kotlin으로 구현

dico.me

[Kotlin] Algorithm - The remaining operational distribution law - Dico

모듈러 산순 분배 법칙

dico.me