Lesson 12 of 30
In Progress

# Recursion

Recursion is a programming technique in which a function calls itself with a modified version of its arguments. This allows the function to repeat a certain task until a certain condition is met, or to perform a task on a smaller input and combine the results to solve a larger problem.

In Python, recursion is implemented using the “return” keyword followed by the function name and modified arguments. It is important to include a base case in the function, which is a condition that stops the recursion and returns a result.

## Using Recursion in Python

Let’s see how we can use recursion in Python to solve real-world problems.

For example, consider a scenario where you need to calculate the factorial of a number. The factorial of a number is the product of all the positive integers from 1 to that number. For example, the factorial of 5 is 1 * 2 * 3 * 4 * 5 = 120.

To solve this problem using recursion, you can use the following function:

def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)

result = factorial(5)
print(result)


The output of this code will be “120”.

In the above example, we defined a function called “factorial” that takes one required argument, “n”. The function checks if “n” is equal to “1”, which is the base case. If “n” is equal to “1”, the function returns “1”. If “n” is not equal to “1”, the function returns “n” multiplied by the result of calling the function again with “n-1” as the argument. This recursive process continues until “n” is equal to “1”, at which point the function returns “1” and the recursion stops.

Recursion can be an elegant and concise way to solve problems, especially when the solution involves repeating a certain task or breaking a problem down into smaller subproblems. It can also be easier to understand and debug compared to using looping constructs such as “for” and “while”.

However, it is important to be mindful of the efficiency and memory usage of recursive functions, as they can be slower and consume more memory compared to iterative solutions. It is also important to include a base case in the function to prevent infinite recursion.

## Conclusion

In this article, we learned about recursion in Python and how to use it to solve real-world problems. We saw an example of calculating the factorial of a number using recursion, and we discussed the advantages and considerations of using recursion in Python. With this knowledge, you can use recursion in your Python programs to solve problems elegantly and concisely.

## Exercises

Here are some exercises with solutions to help you practice what you just learned:

#### How do you define a recursive function in Python that calculates the sum of the first “n” positive integers?

To define a recursive function in Python that calculates the sum of the first “n” positive integers, you can use the “def” keyword followed by the name of the function and a parameter. The function should check if the parameter is equal to “1”, which is the base case. If the parameter is equal to “1”, the function should return “1”. If the parameter is not equal to “1”, the function should return the parameter plus the result of calling the function again with the parameter minus “1”. The syntax for defining such a function in Python is as follows:

def function_name(n):
if n == 1:
return 1
else:
return n + function_name(n-1)


For example, consider the following code:

def sum_of_numbers(n):
if n == 1:
return 1
else:
return n + sum_of_numbers(n-1)


In the above example, we defined a function called “sum_of_numbers” that takes one required argument, “n”. The function checks if “n” is equal to “1”, which is the base case. If “n” is equal to “1”, the function returns “1”. If “n” is not equal to “1”, the function returns “n” plus the result of calling the function again with “n-1” as the argument. This recursive process continues until “n” is equal to “1”, at which point the function returns “1” and the recursion stops.

#### How do you call a recursive function in Python that calculates the sum of the first “n” positive integers?

To call a recursive function in Python that calculates the sum of the first “n” positive integers, you can specify the name of the function followed by the argument inside a set of parentheses. The syntax for calling such a function in Python is as follows:

function_name(argument)

For example, consider the following code:

def sum_of_numbers(n):
if n == 1:
return 1
else:
return n + sum_of_numbers(n-1)

result = sum_of_numbers(5)
print(result)


The output of this code will be “15”.

In the above example, we defined a function called “sum_of_numbers” that takes one required argument, “n”. When we called the function with the argument “5”, the value of “n” was set to “5” and the function returned the sum of the first “5” positive integers, which is “15”.

#### How do you define a recursive function in Python that calculates the Fibonacci sequence up to the “n”th term?

To define a recursive function in Python that calculates the Fibonacci sequence up to the “n”th term, you can use the “def” keyword followed by the name of the function and a parameter. The function should check if the parameter is equal to “0” or “1”, which are the base cases. If the parameter is equal to “0” or “1”, the function should return “1”. If the parameter is not equal to “0” or “1”, the function should return the result of calling the function again with the parameter minus “1” plus the result of calling the function again with the parameter minus “2”. The syntax for defining such a function in Python is as follows:

def function_name(n):
if n == 0 or n == 1:
return 1
else:
return function_name(n-1) + function_name(n-2)


For example, consider the following code:

def fibonacci(n):
if n == 0 or n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)


In the above example, we defined a function called “fibonacci” that takes one required argument, “n”. The function checks if “n” is equal to “0” or “1”, which are the base cases. If “n” is equal to “0” or “1”, the function returns “1”. If “n” is not equal to “0” or “1”, the function returns the result of calling the function again with “n-1” as the argument plus the result of calling the function again with “n-2” as the argument. This recursive process continues until “n” is equal to “0” or “1”, at which point the function returns “1” and the recursion stops.

#### How do you call a recursive function in Python that calculates the Fibonacci sequence up to the “n”th term?

To call a recursive function in Python that calculates the Fibonacci sequence up to the “n”th term, you can specify the name of the function followed by the argument inside a set of parentheses. The syntax for calling such a function in Python is as follows:

function_name(argument)

For example, consider the following code:

def fibonacci(n):
if n == 0 or n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)

result = fibonacci(5)
print(result)


The output of this code will be “8”.

In the above example, we defined a function called “fibonacci” that takes one required argument, “n”. When we called the function with the argument “5”, the value of “n” was set to “5” and the function returned the “5”th term in the Fibonacci sequence, which is “8”.

#### How do you define a recursive function in Python that calculates the greatest common divisor (GCD) of two numbers?

To define a recursive function in Python that calculates the greatest common divisor (GCD) of two numbers, you can use the “def” keyword followed by the name of the function and two parameters. The function should check if the second parameter is equal to “0”, which is the base case. If the second parameter is equal to “0”, the function should return the first parameter. If the second parameter is not equal to “0”, the function should return the result of calling the function again with the second parameter as the first parameter and the remainder of the first parameter divided by the second parameter as the second parameter. The syntax for defining such a function in Python is as follows:

def function_name(a, b):
if b == 0:
return a
else:
return function_name(b, a % b)


For example, consider the following code:

def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)


In the above example, we defined a function called “gcd” that takes two required arguments, “a” and “b”. The function checks if “b” is equal to “0”, which is the base case. If “b” is equal to “0”, the function returns “a”. If “b” is not equal to “0”, the function returns the result of calling the function again with “b” as the first parameter and the remainder of “a” divided by “b” as the second parameter. This recursive process continues until “b” is equal to “0”, at which point the function returns “a” and the recursion stops.