Function parameter that is only available in recursion

Evolution Discussion
1

Currently, if you implement a recursion function, you would do something similar to this:

extension Array where Element: Comparable {
  
  func search(for value: Element, in range: Range<Index>? = nil) -> Index? {
    let range = range ?? startIndex..<endIndex
    guard range.lowerBound < range.upperBound else { return nil }
    
    let size = distance(from: range.lowerBound, to: range.upperBound)
    let middle = index(range.lowerBound, offsetBy: size / 2)
    
    if self[middle] == value {
      return middle
    } else if self[middle] > value {
      return search(for: value, in: range.lowerBound..<middle)
    } else {
      return search(for: value, in: middle + 1..<range.upperBound)
    }
  }
  
}

// [2, 3, 4, 8].search(for: 7)
// [2, 3, 4, 8].binarySearch(for: 7, in: ???)

The range parameter is intended for internal use, that's for recursive call, and to hide this from out world callers, something similar to this can be done:

  func search(for value: Element) -> Index? {
    
    func binarySearch(for value: Element, in range: Range<Index>? = nil) -> Index? {
      let range = range ?? startIndex..<endIndex
      guard range.lowerBound < range.upperBound else { return nil }
    
      let size = distance(from: range.lowerBound, to: range.upperBound)
      let middle = index(range.lowerBound, offsetBy: size / 2)
      
      if self[middle] == value {
        return middle
      } else if self[middle] > value {
        return binarySearch(for: value, in: range.lowerBound..<middle)
      } else {
        return binarySearch(for: value, in: middle + 1..<range.upperBound)
      }
      
    }
    
    return binarySearch(for: value)
  }

You may keep binarySearch(for:in:) out side search(for:) with private keyword.

But, I had an idea, which I'm not sure if it's even possible, is that we introduce a new keyword that makes a parameter only visible for recursion. Which might look something similar to this:

  private func binarySearch(for value: Element, @recursion in range: Range<Index>? = nil) -> Index? {
    // implementation
  }

What do you think? Is it even possible?

2

Hello. To me, it looks that you get bitten by your own quest for convenience.

The code smell lies in the first line of your binarySearch inner function. The range argument is only optional in order to support your sugar:

func search(for value: Element) -> Index? {
  func binarySearch(for value: Element, in range: Range<Index>? = nil) -> Index? {
    let range = range ?? startIndex..<endIndex // <-- there
    ...
  }  
  return binarySearch(for: value)
}

But binarySearch does not want an optional range. It really needs one. That's precisely the point of a binary search.

The same code could simply be rewritten as below, where all intents and algorithms are clearly expressed:

func search(for value: Element) -> Index? {
  return binarySearch(for: value, in: startIndex..<endIndex)
}
private func binarySearch(for value: Element, in range: Range<Index>) -> Index? {
  ...
}

Programming needs sugar, but not everywhere. Think of at as cake icing: it's nice on the visible (public) area of your APIs. But when the whole cake is full of sugar, the recipe becomes very fuzzy and uneasy to digest.

3 Likes
3

It's definitely possible. But that doesn't mean it's a good idea. As the example shows, binarySearch is an implementation detail. And private methods or nested functions are exactly intended for implementation details. I don't think it's a good idea to introduce a new keyword just for the sake of exposing an implementation detail in the public interface, while simultaneously preventing callers for accessing it.

4

I use this convention which I came across at university. Give the externally called function a name and then use the same function name with an R suffix to denote the internal recursive part eg.

func search(for value: Element) -> Index? {
    return searchR(for: value, in: fullRange)
}

private func searchR(for value: Element, in range: Range) -> Index? {
    if found {
        return index 
    } else if baseCase {
        return nil
    } else {
        return searchR(for value, in refinedRange)
    }
}
5

I often nest helper methods like this:

func search(for value: Element) -> Index? {
    func _search(for value: Element, in range: Range<Index>) -> Index? {
        guard range.lowerBound < range.upperBound else { return nil }

        let size = distance(from: range.lowerBound, to: range.upperBound)
        let middle = index(range.lowerBound, offsetBy: size / 2)

        if self[middle] == value {
            return middle
        } else if self[middle] > value {
            return _search(for: value, in: range.lowerBound..<middle)
        } else {
            return _search(for: value, in: middle + 1..<range.upperBound)
        }
    }

    return _search(for: value, in: startIndex..<endIndex)
}
1 Like
6

In this case, if you generalize your code to extend RandomAccessCollection where Element: Comparable, you can perform the recursive calls on a slice of the collection instead of using a range parameter at all:

extension RandomAccessCollection where Element: Comparable {
  func search(for value: Element) -> Index? {
    if isEmpty { return nil }
    
    let middle = index(startIndex, offsetBy: count / 2)
    
    if self[middle] == value {
      return middle
    } else if self[middle] > value {
      return self[..<middle].search(for: value)
    } else {
      return self[index(after: middle)...].search(for: value)
    }
  }
}

This works because slices share the indices of their underlying collection—myArray[5..<10].startIndex is 5, not 0. That means the indices you get by searching a slice can also be used on the original collection.

There are lots of other recursive algorithms where this wouldn’t apply, of course. But Swift already has several general-purpose features that help you handle this nicely; there’s no need for a specific one just for extra recursive parameters.

4 Likes