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!