5. Рекурсия

5. Рекурсия

Функция рекурсии — это функция, которая вызывает сама себя.

Факториал!

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

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

Нахождение числа Фибоначчи

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

Вычисление длины строки

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

Выходная строка в обратном порядке

func reverse_String(_ 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) + reverse_String(String(str_remain))
  }
}
reverse_String("abcdef")

Получение двоичного числа

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

Последовательная сортировка

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)

Бинарный поиск

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)