Problem Solving #1: No Loops Allowed!

How do you write from 100 to 1 without using loops?

– HS (via slack)

Before you read on – think for a minute, how you would solve this programming challenge?

The key point is to realize that anything that can be done using loops can be achieved using recursion (this is also why languages like Haskell, Scheme, and SML do not have any in-built looping constructs). But first, let’s take a look at what recursion is.

What Is Recursion?

Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller subproblems until you get to a small enough problem that it can be solved trivially. Usually, recursion involves a function calling itself.

https://runestone.academy/runestone/books/published/pythonds/Recursion/WhatIsRecursion.html

From the above definition, we can infer three important guidelines to write recursive functions

• We must define the smallest sub-problem that can be solved trivially, this is also known as the base case.
• If the input is not trivial to solve (general case) we must break it down into a smaller problem.
• When calling the function recursively, we must change at least one input variable so that it is closer to the base case.

Using this knowledge we can transform the challenge question into the following code

def count_down(number):
     if number <= 1:
         print(1) # base case
     else
         print(number, end=" ") # general case
         count_down(number-1) # one-step closer to base case 
 print(count_down(100))

And this is how you print 100 to 1 without using a loop!

Loops Vs Recursion

Let’s take another problem, but this time we will write two solutions – one using loops and the other using recursion. Suppose we wanted to sum the first 100 numbers. Using an iterative approach we could write

def iterative_sum():
     result = 0
     for number in range(1, 101):
         result += number
     return result

And a recursive solution would look like this

def recursive_sum(number):
     if number <= 0:
         return 0
     else:
         return number + recursive_sum(number-1)

Although the two solutions return the same result there are a few disadvantages to this form of recursion

• Recursion is slower
  When we compare the two function we can see that the first approach goes through only 100 iterations before returning the result whereas the recursive solution has almost twice that many functions calls to itself before returning the result.
• Recursion can lead to stack overflows
  As each function is called a frame is created on the stack and when it returns the frame is popped off the stack. If the input to the function is large, this can cause an overflow.

Optimizing Recursion With Tail Calls

Using tail recursion we can eliminate the disadvantages of linear recursion and make it so that our solution is as efficient as a loop.
We can do this by using a tail call in our function. A tail call is nothing but a function call that is executed as the last statement of a function.

In code, it would look like this

def tail_sum(number, result):
     if number < 1:
         return result
     else:
         return tail_sum(number-1, result+number)

Comparing our two recursive functions we see that they both generate very different shapes!

Over here you will see that there is the same number of function calls as they are iterations in our loop version. Having a function call at the end also lets the compiler know that there are no more statements to execute and that it does not need to create a frame on the stack.

By using tail calls we can make recursion just as efficient as loops.

This was a question that was posted by Harishankar in the problem-solving channel a few days ago (thanks HS!). Its where we share CS concepts and techniques so if you like learning new ideas, please join us on Slack!