We must print an english ruler using recursion . An english ruler is ruler where each unit has a number of tick. a unit can be divided into smaller units at 1/2 the interval 1/4 the interval 1/8 the interval , for each smaller unit , we must remove one tick .

# an example of english ruler of length 2 # each unit is formed of 4 ticks ---- 2 - -- - --- - -- - ---- 1 - -- - --- - -- - ---- 0

# an english ruler with length of three # each unit is formed of 4 ticks ----- 3 - -- - --- - -- - ---- - -- - --- - -- - ----- 2 - -- - --- - -- - ---- - -- - --- - -- - ----- 1 - -- - --- - -- - ---- - -- - --- - -- - ----- 0

Table of Contents

## The english ruler algorithm

# in this example we want to generate a ruler # which has a length of 1 inch # and where the inch has a five ticks ----- 1 - -- - --- - -- - ---- - -- - --- - -- - ----- 0

we notice that we need to generate this series

The first number five represents a full unit , so it represents the zero unit , and the second number five represents a full unit , the 1 inch unit . So we want to generate the units between [0-1].

These units can be represented by using a string . We notice that

- when the string has a length of zero or when it has a length which is odd , we must insert a new number . We start counting from n = zero. So the number that we must insert is n+1 , so it is is 1 , 2 , 3 , 4
- when the string has a length of even , we must concatenate this string with itself minus the last number .
- when the string has a length of (2^(5-1)) -1 , we must stop . So when it has a length of ( 2 to the power the number of ticks -1) -1 , we must stop.

## Implementing an english ruler using python

def printRuler(inches, numberOfTickPerInch): ''' print a ruler @param inches : number of inches @param numberOfTickPerInch : number of tick per inche ''' # if inches == 0 or at inch 0 print the inch and stop if inches == 0: printTick(numberOfTickPerInch, inches) # if inch > 0 if inches > 0: # start by printing the full inche , so all the number of ticks printTick(numberOfTickPerInch, inches) # generate the units contained in each inch that we must print for numberStr in generateRulerSeries(2**(numberOfTickPerInch - 1) - 1): # print the ticks in each unit printTick(int(numberStr)) # recursively recall the printRuler with the next inch to print printRuler(inches - 1, numberOfTickPerInch) def printTick(number, unit=-1): ''' print a - @param number number of - to print @param unit full unit if we are at full unit print the number of the unit if the unit number is -1 don t print the unit number ''' if number == 0: if unit != -1: # at full unit print the number of the unit e.g 1 , 2 , 3 print(f' {unit}', end='') print() return print('-', end='') # recursively print the next - till the number of ticks is zero printTick(number - 1, unit) def generateRulerSeries(stop, series='', n=0, generatedSeries={}): '''Generate ruler series @param stop the length of the serie where we must stop @param series the series that we will generate start with the empty serie @param n the increment factor @param generatedSeries the generated series for each stop e.g {15: '121312141213121'} used for caching so we generate the serie only once , if the 15 series is already generated return it else generate it and store it inside the dictionary ''' # check if we have already generated the series if so return it if generatedSeries.get(stop) is not None: return generatedSeries[stop] if len(series) == stop: generatedSeries[stop] = series # if the serie has a length of stop stop ad return the generated serie return series if len(series) % 2 == 1 or len(series) == 0: # if the length of the serie is 0 or is odd add the next n return generateRulerSeries(stop, f'{series}{n+1}', n+1) else: # if the lenth of the serie is even concatenate this serie with itself minus the last element return generateRulerSeries(stop, f'{series}{series[0:len(series)-1]}', n)

printRuler(3, 4) ---- 3 - -- - --- - -- - ---- 2 - -- - --- - -- - ---- 1 - -- - --- - -- - ---- 0

printRuler(2, 2) -- 2 - -- 1 - -- 0

## Implementing an english ruler using swift

import Darwin /* @param _ stop : Int the length of the serie where we must stop @param _ series : String the series that we will generate start with the empty serie @param _ n : Int the increment factor @return String @perform generate a ruler serie */ func generateRulerSeries(_ stop : Int, _ series : String = "", _ n: Int = 0) -> String{ if series.count == stop{ //if the serie has a length of stop stop ad return the generated serie return series } if series.count % 2 == 1 || series.count == 0{ //if the length of the serie is 0 or is odd add the next n return generateRulerSeries(stop, "\(series)\(n+1)", n+1) } else{ //if the lenth of the serie is even concatenate this serie with itself minus the last element return generateRulerSeries(stop, "\(series)\(series[series.startIndex ..< series.index(series.endIndex , offsetBy: -1)])", n) } } /* @param _ number : Int number of - to print @param _ unit:Int if we are at full unit print the number of the unit if -1 don't print the full unit @perform print a - */ func printTick(_ number : Int , _ unit : Int = -1){ if number == 0{ if unit != -1{ //at full unit print the number of the unit e.g 1 , 2 , 3 print(" \(unit)" , separator :"" , terminator : "") } print() return } print("-", separator :"" , terminator : "") //recursively print the next - till the number of ticks is zero printTick(number - 1, unit) } /* @param _ inches :Int number of inches @param _ numberOfTickPerInch : Int number of tick per inches @performs : print a ruler */ func printRuler( _ inches : Int, _ numberOfTickPerInch : Int ){ //if inches == 0 or at inch 0 print the inch and stop if inches == 0{ printTick(numberOfTickPerInch, inches) } //if inch > 0 if inches > 0{ //start by printing the full inche , so all the number of ticks printTick(numberOfTickPerInch, inches) //generate the units contained in each inch that we must print for numberStr in generateRulerSeries(Int(pow(2.0 , Double(numberOfTickPerInch - 1)) ) - 1 ){ //print the ticks in each unit printTick(Int(String(numberStr))!) } //recursively recall the printRuler with the next inch to print printRuler(inches - 1, numberOfTickPerInch) } }

#printRuler(2, 4) ---- 2 - -- - --- - -- - ---- 1 - -- - --- - -- - ---- 0