Assignment: PYTHON 2. Lee has discovered what he thinks is a clever recursive st

Question

Assignment: PYTHON

2. Lee has discovered what he thinks is a clever recursive strategy for printing the elements in a sequence (string, tuple, or list). He reasons that he can get at the first element in a sequence using the 0 index, and he can obtain a sequence of the rest of the elements by slicing from index 1. This strategy is realized in a function that expects just the sequence as an argument. If the sequence is not empty, the first element in the sequence is printed and then a recursive call is executed. On each recursive call, the sequence argument is sliced using the range 1:. Here is Lee’s function definition: Write a script that tests this function and add code to trace the argument on each call. Does this function work as expected? If so, explain how it actually works, and describe any hidden costs in running it.

Explanation / Answer

Below is the code snippet for this requirement. Please give tab spaces as they are, because python is tab specific.

def trace_elements(lis, ind):
<TAB> if(ind==len(lis)):
<TAB><TAB> return
<TAB> else:
<TAB><TAB> print lis[ind]
<TAB><TAB> trace_elements(lis,ind+1)
  
trace_elements([1,2,3,4,5,6,7],0)

The algorithm specified in above is absolutely correct. But while using recursion therer should be some condition to terminate the recursive otherwise it might lead to call the same function infinitely, which makes the stack to overflow. So We need to add one condition to terminate when the index of the list reached the length of the list.

This program has one function called trace_elements which takes two aguments, one is list and the other is index of the elements.

Each time we call the recursion we will increment the index by one and print the element at that index. When the index reaches length of the list we will terminate the program.

This program will run with a complexity of O(log n), as it is using recursion.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.