Siddharta Govindaraj
/home/siddhi

/home/siddhi

Recursion Part 5: Exercises in tail recursion

Siddharta Govindaraj's photo
Siddharta Govindaraj
·Apr 19, 2022·

1 min read

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)

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
 
Share this