# Recursion Part 5: Exercises in tail recursion

Siddharta Govindaraj
·Apr 19, 2022·

Is this tail recursion?

``````def fibonacci(n):
if (n <= 2):
return 1
return fibonacci(n - 2) + fibonacci(n - 1)
``````

``````def find_root(node):
if node.parent is None:
return node
return find_root(node.parent)
``````

And this?

``````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
``````