Recursion

Introduction

A recursion function is a function that calls itself.

1. Factorial !

func factorial(_ n: Int) -> Int {
    if n > 1 {
        return n * factorial(n - 1)
    } else {
        return 1
    }
}

print(factorial(5))

2. X^n

func toThePowerOfN(_ X: Int, _ n: Int) -> Int {
    if n > 1 {
        return X * toThePowerOfN(X, n - 1)
    } else {
        return X
    }
}

print(toThePowerOfN(2, 5)) // 2^5

3. Finding Fibonacci Number

func fibonacciNumber(_ n: Int) -> Int {
    if n == 0 {
        return 0
    } else if n == 1 {
        return 1
    } else {
        return fibonacciNumber(n - 2) + fibonacciNumber(n - 1)
    }
}

print(fibonacciNumber(10))

4. String Length Calculation

func stringLengthCalculation(_ str: String) -> Int {
    if str == "" {
        return 0
    } else {
        var str_temp = str
        str_temp.remove(at: str_temp.startIndex)
        return 1 + stringLengthCalculation(str_temp)
    }
}

stringLengthCalculation("asdfddddddg")

5. Output String in Reverse

func reverseString(_ str: String) -> String {
    if str == "" {
        return ""
    } else {
        let str_last = str[str.index(before: str.endIndex)]
        let str_remain = str[str.startIndex..<str.index(before: str.endIndex)]
        return String(str_last) + reverseString(String(str_remain))
    }
}

reverseString("abcdef")

6. Getting Binary Number

func binaryNumber(_ number: Int) -> String {
    if number < 2 {
        return String(number)
    } else {
        return binaryNumber(number / 2) + String(number % 2)
    }
}

binaryNumber(546)

7. Sequential Search

func sequentialSearch(_ data: [Int], _ begin: Int, _ end: Int, _ target: Int) -> Int {
    if begin > end {
        return -1
    } else if target == data[begin] {
        return begin
    } else {
        return sequentialSearch(data, begin + 1, end, target)
    }
}

sequentialSearch([1, 2], 0, 1, 2)

8. Binary Search

func binarySearch(_ data: [Int], _ begin: Int, _ end: Int, _ target: Int) -> Int {
    if begin > end {
        return -1
    } else {
        let middle = (begin + end) / 2
        if data[middle] == target {
            return middle
        } else if target > data[middle] {
            return binarySearch(data, middle + 1, end, target)
        } else {
            return binarySearch(data, begin, middle, target)
        }
    }
}

binarySearch([1, 2, 3, 4, 5, 6], 0, 5, 3)