CSC300 / CSC402: Recursive version (forward) [7/14] |
Replacing a while loop with a recursive function call:
For // list[i..]==[5,11,5,5], result==0 // list[i..]==[11,5,5], result==1 // list[i..]==[5,5], result==1 // list[i..]==[5], result==2 // list[i..]==[], result==3 The call/return pattern is: // call@3 ([5,11,5,5], 0) // call@4 ([11,5,5], 1) // call@5 ([5,5], 1) // call@6 ([5], 2) // call@7 ([], 3) // retn@7 ([], 3) : 3 // retn@6 ([5], 2) : 3 // retn@5 ([5,5], 1) : 3 // retn@4 ([11,5,5], 1) : 3 // retn@3 ([5,11,5,5], 0) : 3
(Abbreviating Converted to a recursive function. Note that we do not mutate i in the helper! Note that computation goes forward. We forget the old values of i as we go forward. This kind of recursion is called tail recursion: the recursive call is the last thing the function does before it returns. There's no work to do after the recursive call returns. There is a one-to-one correspondence between loops and tail-recursive functions. We can mechanically convert between these to forms. Compilers do it all the time. In the language I work in, Scala, the compiler can be instructed to expect to be able to do tail-call elimination. |