An Approach
lWrite iterative pseudo-code,
then construct recursive equivalent.
then construct recursive equivalent.
lL = É list to be converted É;
Result = 0;
while( L != [ ] )
{
Result
= 2*Result + first(L);
L
= rest(L);
}
É answer is in Result ...
Result = 0;
while( L != [ ] )
{Result
= 2*Result + first(L);L
= rest(L);}É answer is in Result ...
lDefining fromBinary3(L, Result):
lfromBinary3([], Result) => Result;
lfromBinary3([F | R], Result) =>
fromBinary3(R,
2*Result+F);
fromBinary3(R,
2*Result+F);lfromBinary(L) = fromBinary3(L, 0);
lfromBinary3([1, 0, 0, 1, 0, 1], 0) ==>
lfromBinary3([0, 0, 1, 0, 1], 1) ==>
lfromBinary3([0, 1, 0, 1], 2) ==>
lfromBinary3([1, 0, 1], 9) ==>
lfromBinary3([0, 1], 9) ==>
lfromBinary3([1], 18) ==>
lfromBinary3([], 37) ==>
l37