 # Recursive functions, reaching base case once vs many times / returning something unique from the last call

Hi,

I was wondering whether there’s a way to return something only in the final base case of a recursive function, or perhaps when the call stack is empty or reaches `__main__` or whatever the best approach may be.

I found that this easily works for some simpler recursive functions such as the factorial one.

Recursive factorial function
``````def factorial(n, times=0):
if n == 1 or n == 0:
print(f"The function has run {times} times")
return n

times += 1
return n * factorial(n-1, times)

factorial(15)

# prints 'the function has run 14 times'
``````

However, it goes out of hand for more complex recursive functions (because of multiple calls in the same level I guess, but they may be other cases), where the recursion trees ends up with many trips to the base case.

Recursive fibonacci function
``````def fibonacci(n):
if n < 0:
return
if n <= 1:
print("The function has ended")
return n

return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(10))

# prints 'the function has ended' as many times as the base case is reached
``````
Quicksort function from the final sorting project
``````def quicksort(list, start, end, comparison_function, swaps=0):
if start >= end:
print(f"Number of swaps: {swaps}")
return
pivot_idx = random.randrange(start, end + 1)
pivot_element = list[pivot_idx]
list[end], list[pivot_idx] = list[pivot_idx], list[end]
less_than_pointer = start
for i in range(start, end):
if comparison_function(pivot_element, list[i]):
list[i], list[less_than_pointer] = list[less_than_pointer], list[i]
less_than_pointer += 1
swaps += 1
list[end], list[less_than_pointer] = list[less_than_pointer], list[end]
quicksort(list, start, less_than_pointer - 1, comparison_function, swaps)
quicksort(list, less_than_pointer + 1, end, comparison_function, swaps)
``````
1 Like

Something like tail recursion?

2 Likes

After a bit of quick research, it looks like yes, this could be what I’m looking for!

Can any function be written using tail recursion though? Would it be possible, for example, in the sorting function I posted above?

EDIT: Actually another quick research led me directly to the answer to my question. I wonder if there are other ways to achieve this.

1 Like

Interesting! what did you need it for?

As I was doing the sorting exercise in the course, I wanted to find a way to give me the number of swaps the quicksort needed to make, to have a concrete way to compare it to bubble sort.

I found something called continuation passing style, which might do what I want, but I don’t know yet where to start understanding it.

I’m sure MIT Opencourseware has some dedicated courses to algorithms and implementations if you’re interested. I think there are some other university channels with great material as well.

Yes they do! As it happens, I’ve actually been checking them out in the last few days. I’m still not ready to take the full plunge into algorithms, it’s just a passing curiosity. But they’re definitely pretty interesting!