Recursive Programming Basics

Question

What is a recursive function and how is it implemented in Python?

Answer 1

When a function calls itself again and again than it is called recursion.

consider below code where we are printing table of 10 without using any loop.

Here add function recall itself if sum is less than 100. Let me know if you need any clarification.

def add(x,sum):

sum=sum+x

print (sum)

if (sum<100):

add(x,sum)

return sum

result=add(10,0)

Answer 2

Recursion refers to programs that will run iterations of themselves in a series until a solution is found. This can be very helpful for problems where a simple task is going to be repeated an unknown number of times. To set up a recursive function, we can use an if statement that either updates the result using the same function, or return the current result as is.

For example, if we needed to find the sum of all numbers from 1 to x, squared:

# Not using Recursion:

def find_sum(x):

sum = 0

for num in range(0, x + 1):

sum += num*num

return sum

# Using Recursion

def find_sum(x):

if x > 1:

return x*x + find_sum(x-1)

elif x == 1:

return x

Recursion can often help us condense our code into fewer lines. For example, using recursion can allow us to reduce the function above to a single lambda function.

# Lambda function for finding sum of squares

find_sum = lambda x: x*x + find_sum(x-1) if x>1 else x

While knowing how to use recursion is important, actually using it is often times not beneficial. The recursive functions shown here take more time to run than the non-recursive example. This is because recursion requires more information to be stored in memory for the duration. It can be visualized like this:

Input=4 --> find_sum(4)--> find_sum(3) --> find_sum(2) --> find_sum(1)

Result=30 <-- 4*4 + <-- 3*3 + <-- 2*2 + <-- 1*1

Each recursive layer must be stored in memory until the final layer is reached. The results from each layer must then be passed back through each layer. This can give the recursive functions a logarithmic complexity when the non-recursive alternative is linear. For example, while the difference in speed for finding the sum of squares with x=4 are minimal, the difference when solving for larger numbers is substantial. The recursive examples here take over twice as long when x=1000!

Programming compilers have built in protections to prevent excessive recursion. In Python, the default maximum recursion depth is 1000. If you try to use a function that creates more layers than the maximum recursion depth, you will receive an error message. This is another reason to avoid using recursion.

That being said, in the right situation, recursion is a powerful tool that can help solve complex problems. If you are interested in studying this topic further, you might want to look up the difference between head- and tail-recursion. Using head recursion can limit the amount of information being stored in each layer, and improve the speed.

As a side note, using list comprehension is generally much faster than for-loops and can also help reduce simple functions to a single line. This next example is both the fastest and most condensed solution I have found to the example problem:

# Using list comprehension for speed

find_sum = lambda x: sum([_*_ for _ in range(x+1)])

Thanks for reading, and good luck!