Character Count Function Recursively

//
//  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.

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.

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

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

Cheers, that's great, thanks very much.

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

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

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

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
}

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:

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.

Terms of Service

Privacy Policy

Cookie Policy