Recursion examples in swift

A function which calls itself in the body & solve the problem is called recursion. we will take some example to understand

1. Print 1 to N
2. Print N to 1
3. Sum of first n numbers
4. Check if String is Palindrome.
5. Create Factorial of a number
6. Get Fibonacci nth Number
7. Calculate Power of two
8. Calculate Power of four

#1 Print numbers from 1 to N

func printNumersFromOneToN(_ n: Int) {
    if n <= 0 { return }
    printNumersFromOneToN(n-1)
    print(n, terminator: " ")
}

Because Print is before recursion function it will print 1 to n

#2 Print numbers from N to 1

func printNumersFromNtoOne(_ n: Int) {
     if n < 1 { return }
    print(n, terminator: " ")
    printNumersFromNtoOne(n-1)
}
printNumersFromNtoOne(5)

#3 Sum of first N numbers

var sumValue = 0
func sumOfFirstNNumbers(_ n: Int) -> Int {
    if n < 1 { return sumValue }
    sumValue += n
    return sumOfFirstNNumbers(n-1)
}
let op = sumOfFirstNNumbers(5)
print("op", op)// 15

#4 Check if string is Palindrome

// Approach #1
func checkPalindrom(_ str: inout String) -> Bool {
  if str.count < 2 {
    return true
  } else {
    if str.removeFirst() != str.removeLast() {
      return false
    } else {
        return checkPalindrom(&str)
    }
  }
}
var inputStr = "nitin"
let isPalidrom = checkPalindrom(&inputStr)
print("isPalindrom-->", isPalidrom)

// Approach #2

func checkPalindrome<T: StringProtocol>(_ str: T) -> Bool {
    if str.count < 2 {
        return true
    } else {
        if str.first == str.last {
            let start = str.index(str.startIndex,offsetBy: 1)
            let end = str.index(str.endIndex,offsetBy: -1)
            return checkPalindrome(str[start..<end])
        } else {
            return false
        }
    }
}
checkPalindrom(&inputStr)

// Approach #3: Non recursive
extension StringProtocol {
  subscript(_ offset: Int) -> Element {
      self[index(startIndex, offsetBy: offset)]
  }
}

func isPalindrome(_ word: String) -> Bool {
    let word = word.filter{ $0 != " " }
    for (i, character) in word.enumerated() {
        if character != word[word.count-i-1] {
            return false
        }
    }
    return true
}
isPalindrome("nitin")

// Approach #4 Non recursive

func isPalindrome4(_ word: String) -> Bool {
    let word = word.filter{ $0 != " " }
    for (i, character) in word.enumerated() {
        let lastChar = word.index(word.startIndex, offsetBy: word.count-i-1)
        if character != word[lastChar] {
            return false
        }
    }
    return true
}
isPalindrome4("nitin")

#5. Create Factorial of a number

// Example 2: Factorial : Example - 4! = 4x3x2x1 = 24

func findFactorial(inputNumber: Int) ->Int {
    if inputNumber == 1 {// Base case
        return 1
    }
    return inputNumber * findFactorial(inputNumber: inputNumber - 1)
}
print("findFactorial:")
print(findFactorial(inputNumber: 3))

When we write a recursive call base case plays important role. when we dropdown to a lower number we just add a check to stop recursive call. Like here we have base case if inputNumber == 1. So Factorial is calculated as 4 * findFactorial(3)= > 4*3*2*1

#6. Get Fibonacci nth Number

// Example 3 Get nth Fabonacci number.. : Fibonacci number 0: 1: 1: 2: 3: 5: 8: 13: 21

func fibonacci(num: Int) ->Int {
    if num <= 1 {
        return num
    }
    // print("in function starts")
    let first = fibonacci(num: num - 1)
    let second = fibonacci(num: num - 2)
    //print("first--->", first)
    //print("second--->", second)
    //print("+++", first+second)
    return first + second
}
print("fibonacci(n--->", fibonacci(num: 4))

Fibonacci is basically addition of current & Next – Fibonacci number 0: 1: 1: 2: 3: 5: 8: 13: 21 & Base case will be if num <= 1 {

#7. Calculate Power of two

// Example 4: Power of 2… 2p0 =1 — 2p1 = 2 — 2p2 = 2 — 2p3 =8 — 2p4 = 16 (p stand for power). We can solve it by using two approaches : –

// Approach #A
func getPowerOfTwo(num: Int) -> Int {
    if num == 0 {
        return 1
    }
    return 2 * getPowerOfTwo(num: num-1)
}
print("getPowerOfTwo", getPowerOfTwo(num: 3))

# Approach B using Bitwise operator 
func checkValidPowerOfTwoWithBitwise(num:Int) -> Bool {
    return num > 0 && (num & (num-1) == 0 )
}
print(checkValidPowerOfTwo(num: 1))

Bit manipulation : bit manipulation techniques are usually based on observations from multiple examples

Binary form of numbers is –
3->0000 0011
4->0000 0100
5->0000 0101
6->0000 0110
7->0000 0111
8->0000 1000
The observation we can conclude is that the number which is a power of two has always compulsory 1 true bit.

Now consider :-
bit representation of 7 -> 0111
bit representation of 8 -> 1000
bitwise AND of 7 and 8 -> 0000
we are gonna use this property for for all numbers which are powers of two
Time Complexity : O(1)
Space Complexity : O(1)