Character Count Function Recursively

Using Swift
1 
//
//  main.swift
//  TmpProj
//
//  Created by Mark King on 24/08/2021.
//

import Foundation

func occurencesOfCharacters(in text: String) -> [Character: Int] {
      var resWithKey : Int
      var partResWithKey: Int
      var res: [Character: Int] = [:]
      var firstIndex = text.startIndex
      if text.count == 0 {
        return [:]
      }
      if text.count == 1 {
        res[text[firstIndex]] = 1
        return res
      } else if text.count > 1 {
        var result: [Character: Int] = [:]
        var partialResult: [Character: Int] = [:]
        var char = text[text.index(text.startIndex, offsetBy: 0)]
        for char2 in text.dropFirst() {
            if( char2 == char) {
                result[char2, default: 0] += 1
            }
        }
        partialResult = occurencesOfCharacters(in: String(text.dropFirst())) //
        // Append the two dictionaries together
        
        for( key, value) in partialResult {
            // Key has been found in the dictionary, remember the value\
            guard var resWithKey = result[key], let partResWithKey = partialResult[key] else {

                }
            resWithKey = resWithKey + partResWithKey
            
            }
        return resWithKey
        }
        
      }
      // <2>
let string: String = "Here is a string"
var result: [Character: Int] = [:]
result = occurencesOfCharacters(in: string)
for( key, val) in result {
    print("\n\(key),\(val)")
}

This is my 2nd attempt at counting the items recursively, I think I got the right idea and I just haven't implemented correctly yet. For some reason it is impossible to return [Character:Int]. The value is out of scope and in the wrong format anyway.

2

No, it's impossible to return anything other than [Character: Int] because that's the declared return type of the function. You're trying to return an Int: return resWithKey. If you option-click on a variable in Xcode, it tells you the type.

3

But because of the way guard is arranged it is impossible to get a value of it.

4

I have absolutely no idea what you're referring to here.

This function should not be recursive. Here's the solution:

func occurrencesOfCharacters(in text: String) -> [Character: Int] {
    return text.reduce(into: [:]) { result, character in
        result[character, default: 0] += 1
    }
}
2 Likes
5

Cheers, that's great, thanks very much.

6

Just to demonstrate that it can be done here is the function using recursion:

func occurencesOfCharacters(in text: String, arrayCount: inout [Character: Int]) -> [Character: Int] {
      var resWithKey : Int
      var partResWithKey: Int
      var res: [Character: Int] = [:]
      var firstIndex = text.startIndex
      if text.count == 0 {
        return [:]
      }
      if text.count == 1 {
        res[text[firstIndex]] = 1
        return res
      } else if text.count > 1 {
        let char = text[firstIndex]
        arrayCount[char, default: 0] += 1
        var partialResult: [Character: Int] = [:]
        partialResult = occurencesOfCharacters(in: String(text.dropFirst()), arrayCount: &arrayCount)
        return arrayCount
        
      }
    return res
}
let string: String = "Here is a string"
var result: [Character: Int] = [:]
    result = occurencesOfCharacters(in: string, arrayCount: &result)
for( key, val) in result {
    print("\n\(key),\(val)")
}
7

No this function doesn't work. It doesn't count the g in the string Here is a string. Even if you want to write a recursive function, there's a much simpler way to do it. Your version contains many unused variables and variables that are never mutated which should be changed to let constants.

func occurrencesOfCharacters<S: StringProtocol>(in string: S) -> [Character: Int] {
    
    if string.isEmpty {
        return [:]
    }

    var partialResult = occurrencesOfCharacters(
        in: string.dropFirst()
    )
    
    partialResult[string.first!, default: 0] += 1
    
    return partialResult
        
}
1 Like
9

Sorry for bikeshedding :nerd_face:

For performance reasons, it's better to use generics:
func occurrencesOfCharacters<S>(in string: S) -> [Character: Int] where S: StringProtocol

When you call it recursively...
var partialResult = occurrencesOfCharacters(in: string.dropFirst())

1 Like
10

Not taking no for an answer it now counts the g and an empty string.

Here is the code:

func occurencesOfCharacters(in text: String, arrayCount: inout [Character: Int]) -> [Character: Int] {
      var resWithKey : Int
      var partResWithKey: Int
      var res: [Character: Int] = [:]
      var firstIndex = text.startIndex
      if text.count == 0 {
        arrayCount = [:]
        return res
      }
      if text.count == 1 {
        arrayCount[text[firstIndex]] = 1
        return res
      } else if text.count > 1 {
        let char = text[firstIndex]
        arrayCount[char, default: 0] += 1
        var partialResult: [Character: Int] = [:]
        partialResult = occurencesOfCharacters(in: String(text.dropFirst()), arrayCount: &arrayCount)
        return arrayCount
        
      }
    return res
}
11

It still doesn't work. It gives the wrong result for abbccc.

I don't know what answer you're referring to. I already demonstrated that it is possible to implement this function using recursion.

Still, your function contains unused variables: resWithKey and partResWithKey. The res and firstIndex variables were never mutated, so they should be let constants. Pay attention to the warnings in Xcode:

Screen Shot 2021-08-31 at 12.03.55 PM
Screen Shot 2021-08-31 at 12.03.55 PM1696×794 182 KB

12

Also keep in mind that IIRC Swift does not guarantee tail call optimzation (and I'm not sure it would apply to your implementation if it did), so a recursive implementation will inevitably exhaust available stack space and crash for longer strings.

This is fine for a toy implementation to explore recursive patterns of course, but a limitation that should be kept in mind any time recursion is considered.

13

Sorry I didn't meant to start an argument. I just love recursion.