Future nano-scale devices are expected to shrink to ever smaller dimensions, to operate at low voltages and high frequencies, to be more sensitive to environmental influences and to be characterised by high dynamic fault rates and defect densities. Fundamentally new fault-tolerant architectures are required in order to produce reliable systems that will operate correctly. Simple replication of micro-architecture blocks will no longer suffice, as all replicated blocks will have faults. The history index of correct computation (HICC) is examined in a recursive and non-recursive fault-tolerant approach at the bit and module levels to identify reliable blocks on-the-fly and forward their computation results, while ignoring results from unreliable blocks. Simulation results show that recursive and non-recursive HICC offers the best resilience to faults when faults are non-uniformly distributed among redundant blocks. A correct computation rate of 99% is achieved using the recursive HICC when decision units at the bit and module levels are fault free, despite an average fault injection rate of 20% compared to a 68% correct computation rate for the recursive triple modular redundancy voter. When faults are injected everywhere in the design, the non-recursive HICC supports the best correct computation percentage. The effect of circuit size and history indices are also examined and discussed.