Try out the following problems: Ask any questions/answers in the comments.
Is this tail recursion?
def fibonacci(n): if (n <= 2): return 1 return fibonacci(n - 2) + fibonacci(n - 1)
What about this?
def find_root(node): if node.parent is None: return node return find_root(node.parent)
def find_node(node, data_to_find): if node is None: return None if node.data == data_to_find: return node return find_node(node.next, data_to_find)
Try converting the above three programs to iterative versions. Do you find some harder than the others?
Now lets do the reverse. Convert this iterative program into a tail recursive version. First convert it to an accumulator based function and then convert that to an ordinary tail recursive version. Hint: First convert the for loop into a while loop.
def sum_of_first_n_numbers(n): sum = 0 for i in range(n + 1): sum = sum + i return sum
How about this one? Assume all numbers are positive (> 0). Hint: The accumulator does not always have to perform some mathematical operation. It can also be used to keep track of the state so far.
def find_max(number_list): maximum = 0 for num in number_list: if num > maximum: maximum = num return max