recursion problem returns for exampleconsider the function in listing which printed the contents of linked list in reverse order we had to save reference to each node until the recursive process began unwindingat which time the node values could be printed by using recursionthese references were automatically pushed onto the run time stack as part of the activation record each time the function was called now suppose we implement recursive function to print the items of linked list in order from beginning to end instead of using simple loop structuredef printinordernode )if node is not none printnode data printinordernode next this function eliminates the need for loop to iterate through the listbut do we have anything to save on the stack until the recursive call returnsthe answer is no when the recursive call returnsthe function is finished and it simply returns this is an example of tail recursionwhich occurs when function includes single recursive call as the last statement of the function in this casea stack is not needed to store values to be used upon the return of the recursive call and thus solution can be implemented using an iterative loop instead recursive applications there are many applications that can be solved using recursion some in factcan only be solved using recursion in this sectionwe introduce some of the classic problems that require the use of recursion or can benefit from recursive solution recursive binary search the binary search algorithmwhich we introduced in improves the search time required to locate an item in sorted sequence we provided an iterative implementation of the binary search algorithm in but the algorithm can also be implemented recursively since it can be expressed in smaller versions of itself in searching for target within the sorted sequencethe middle value is examined to determine if it is the target if notthe sequence is split in half and either the lower half or the upper half of the sequence is examined depending on the logical ordering of the target value in relation to the middle item in examining the smaller sequencethe same process is repeated until either the target value is found or there are no additional values to be examined recursive implementation of the binary search algorithm is provided in listing as with the earlier versionthis version also works with virtual subsequences instead of physically splitting the original sequence the two argumentsfirst and lastindicate the range of elements within the current virtual subsequence on the first call to the functionthese values are set to the full range of the original sequence