CSC300 / CSC402: Recursive version (backward) [9/14] |
Recursion is more general than looping!
For // list[i..]==[], result==0 // list[i..]==[5], result==1 // list[i..]==[5,5], result==2 // list[i..]==[11,5,5], result==2 // list[i..]==[5,11,5,5], result==3 The call/return pattern is: // call@3 ([5,11,5,5]) // call@4 ([11,5,5]) // call@5 ([5,5]) // call@6 ([5]) // call@7 ([]) // retn@7 ([]) : 0 // retn@6 ([5]) : 1 // retn@5 ([5,5]) : 2 // retn@4 ([11,5,5]) : 2 // retn@3 ([5,11,5,5]) : 3 The immediate recursive call here is often referred to as the leap of faith. You're assuming you can solve the problem for the rest of the list. |