[Kotlin] Algorithm - Recursive

2023-10-16 19:57 (KST)

Language :

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)
}