Como determinar o tamanho do período de uma dízima periódica da forma 1/n?

O "vetor de sucessores" que você diz é um vetor que vai guardando um valor autoincrementante na posição dos restos que vão saindo? Quer dizer, no caso do 1/7 seria [nil, 5, 1, 0, 3, 4, 2]? Se você para quando acha alguém marcado (i.e., quando acha um ciclo), não é só pegar nesse momento o valor do autoincrementante (+1, se começou do zero) e você tem o tamanho do período? Por que precisa da busca em profundidade?

Repare que se o algoritmo fosse da maneira que você propõe ele estaria errado. O vetor de sucessores é INDEXADO por \([0,n)\), ou seja, cada posição do vetor representa um dos restos possíveis. A divisão longa gera uma sequência de restos, se em uma dada iteração \(i\) o resto gerado é \(a_i\), então fazemos vetor[\(a_{i-a}\)] = \(a_i\).

Ops, tem um typo no meu último comentário. O certo é vetor[\(a_{i-1}\)] = \(a_{i}\)

Sim, o meu vetor também é indexado por \([0,n)\). Se em uma dada iteração \(i\) o resto gerado é \(a_i\), eu faço vetor[\(a_i\)] = i++, mas antes verifico: if vetor[\(a_i\)] != nil; break, e o resultado do tamanho é \(i\).

Na verdade o que você armazena no vetor é irrelevante, ele só precisa ter algum marcador indicando se a posição já foi usada ou não. Eu poderia só inicializar tudo com 0 e colocar 1 quando eu já passei por lá, mantendo a contagem de \(i\) fora do vetor. Aí quando eu chegasse em um 1 eu simplesmente imprimia a contagem.

Se eu entendi o que você escreveu, não dá para marcar apenas um, da forma como foi proposto (\(O(n)\)) porque há casos onde parte dos restos não entra na conta. Então, quando temos, por exemplo, \(\frac{1}{6} = 0,166666...\), da forma como foi especificado, o vetor ficaria [0,1,0,1,0,0], e ele responderia (incorretamente) que o período tem tamanho 2 (quando o tamanho do período é 1).

O que você poderia fazer para otimizar (i.e., não percorrer novamente o vetor todo) é armazenar um contador geral (o \(i\)), e no vetor de 0s escrever em que momento você chegou pela primeira vez naquele resto (ou seja, o valor de \(i\) naquele momento). Então, quando você chega num elemento \(k\) diferente de zero, a diferença \(i - v[k]\) determina o tamanho do período.