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)