Algorithms Explained #1: Recursion | by Claudia Ng | Oct, 2022
Understand when and how to use recursive solutions with examples in Python
This is the first article in a series on explaining algorithms with examples in Python. This is intended for aspiring Data Scientists and Software Engineers or those wishing to brush up on algorithms in preparation for coding interviews.
Recursion is a fundamental concept in programming when learning about data structures and algorithms. In this article, I will explain what recursion is, when to use it and walk through some examples written in Python 3.
What is Recursion?
Recursion is when a function or method calls itself and is essential to the divide and conquer paradigm, whereby the idea is to divide bigger problems into smaller subproblems and the subproblem is some constant fraction of the original problem. The way recursion works is by solving the smaller subproblems individually and then aggregating the results to return the final solution.
When is Recursion Used?
Recursion is frequently used for problems that are recursive in nature. This includes graphs, trees and data structures that have a parent-child relationship. Some canonical examples of recursion problems are calculating the nth Fibonacci number, calculating the factorial of a number, and converting decimal numbers into binary numbers.
Why Should I Use Recursion?
When used correctly, a recursive solution usually results in cleaner code that is easier to read. It is more intuitive when solving solutions that are recursive in nature, as we will see in examples later. However, keep in mind that recursive solutions can be less memory efficient and if your machine’s memory is exhausted or your function’s stack is too deep before reaching the base case, it will cause a stack overflow error.
How Do I Construct a Recursive Algorithm?
To write a recursive algorithm, you will first need to break the problem into two parts — the first is the base case and the second is the recursive step:
- Base case: The base case refers to the condition that needs to be met in order to stop calling the recursive function. This is the end state or the last case to be evaluated before terminating the recursive function and returning a result. Without the base case, your recursive function would go on an infinite loop and never terminate!
- Recursive step: This is the part of the code that makes recursive calls to the same function to compute the results using inputs that update with every recursive call. Every iteration should bring you closer to the base case.
Examples #1: Determining the nth Fibonacci series using recursion
In a Fibonacci series, the first and second term of the series are 0 and 1 respectively. To calculate the number at position n, you can take the sum of the previous two terms, i.e. number at position (n-1) + number at position (n-2). A Fibonacci series F can be represented mathematically as follows:
- F(1) = 0
- F(2) = 1
- F(n) = F(n-1) + F(n-2)
We will define a function fibonacci() that takes a number n as an argument and returns the number at position n in the Fibonacci series. This problem can be solved in multiple ways, but in the recursive solution, we can break the problem down into the following two parts:
- Base case: if n is 1, return 0 since the first term of the Fibonacci series is 0. If n is 2, return 1 since the second term of the series is 1.
- Recursive step: for all other values of n, we can calculate the number at position n by adding together the previous two terms: fibonacci(n-1) + fibonacci(n-2).
Below is the Python implementation of a recursive solution for calculating the nth number in a Fibonacci series:
def fibonacci(n):
if n == 1:
return 0
if n == 2:
return 1
return fibonacci(n-1) + fibonacci(n-2)
Example #2: Calculating the nth factorial
The factorial of the nth number is the product of all integers from 1 to n. For example, the factorial of 5 is 5! = 1 * 2 * 3 * 4 * 5 = 120. Note that the factorial of 0 is 1 and the factorial of negative numbers is undefined.
We will define a function factorial() that takes a number n as an argument and returns the factorial of n. To solve this problem using recursion, we have to break it down into the following two cases:
- Base case: if n = 0 or 1, return 1. If n < 0, return error because factorial for negative numbers is undefined.
- Recursive step: multiple n by the result of the previous term, i.e.
n * factorial(n-1).
Below is the Python implementation of a recursive solution for calculating the nth factorial:
def factorial(n):
if (n == 0 or n == 1):
return 1
if n < 0:
raise Exception("n must be positive. The factorial of a negative number is undefined.")
return n * factorial(n - 1)
Example #3: Displaying a Decimal Integer as Binary
In everyday life, the most commonly used number system is the Decimal number, which has base 10. For digital systems, the binary number system is often used and it has base 2.
One way to convert a decimal number into binary is to divide the number by 2 and record the remainder at every step, then write the remainders in reverse order (from bottom to top) and this is the binary equivalent of your integer. For example, a decimal number 36 in binary is:
36 / 2 = 18 R 0 → 18 / 2 = 9 R 0 → 9/ 2 = 4 R 1 → 4/ 2 = 2 R 0 → 2 / 2 = 1 R 0 → 1/ 2 = 0 R 1
Gathering the remainders in reverse order, we get 100100 as the binary number for the decimal number 36.
We will define a function convert_to_binary() that takes a decimal number n and returns the binary number in the form of a list of integers. To solve this problem recursively, we can break it down into two parts:
- Base case: If n is equal to 0, return a list with an integer 0. If n is equal to 1, return a list with an integer 1.
- Recursive step: Call the function
convert_to_binary()on the quotient (number n divided by 2) and keep track of the remainder from this operation.
Below is the Python implementation of a recursive function to convert decimal numbers to binary numbers:
def convert_to_binary(n):
if n == 0:
return [0]
elif n == 1:
return [1]
remainders = convert_to_binary(n // 2)
remainders.extend([n % 2])
return remainders
Conclusion
Recursion is a fundamental programming concept and is popular with coding interviews. Some common use cases for recursion are data structures with a parent-child relationship. The key to writing a recursive solution is to first define the base case and then think about the recursive step. A recursive one often results in cleaner code but it may not be as memory efficient.
Up next is Algorithms Explained #2: Sorting.
Understand when and how to use recursive solutions with examples in Python
This is the first article in a series on explaining algorithms with examples in Python. This is intended for aspiring Data Scientists and Software Engineers or those wishing to brush up on algorithms in preparation for coding interviews.
Recursion is a fundamental concept in programming when learning about data structures and algorithms. In this article, I will explain what recursion is, when to use it and walk through some examples written in Python 3.
What is Recursion?
Recursion is when a function or method calls itself and is essential to the divide and conquer paradigm, whereby the idea is to divide bigger problems into smaller subproblems and the subproblem is some constant fraction of the original problem. The way recursion works is by solving the smaller subproblems individually and then aggregating the results to return the final solution.
When is Recursion Used?
Recursion is frequently used for problems that are recursive in nature. This includes graphs, trees and data structures that have a parent-child relationship. Some canonical examples of recursion problems are calculating the nth Fibonacci number, calculating the factorial of a number, and converting decimal numbers into binary numbers.
Why Should I Use Recursion?
When used correctly, a recursive solution usually results in cleaner code that is easier to read. It is more intuitive when solving solutions that are recursive in nature, as we will see in examples later. However, keep in mind that recursive solutions can be less memory efficient and if your machine’s memory is exhausted or your function’s stack is too deep before reaching the base case, it will cause a stack overflow error.
How Do I Construct a Recursive Algorithm?
To write a recursive algorithm, you will first need to break the problem into two parts — the first is the base case and the second is the recursive step:
- Base case: The base case refers to the condition that needs to be met in order to stop calling the recursive function. This is the end state or the last case to be evaluated before terminating the recursive function and returning a result. Without the base case, your recursive function would go on an infinite loop and never terminate!
- Recursive step: This is the part of the code that makes recursive calls to the same function to compute the results using inputs that update with every recursive call. Every iteration should bring you closer to the base case.
Examples #1: Determining the nth Fibonacci series using recursion
In a Fibonacci series, the first and second term of the series are 0 and 1 respectively. To calculate the number at position n, you can take the sum of the previous two terms, i.e. number at position (n-1) + number at position (n-2). A Fibonacci series F can be represented mathematically as follows:
- F(1) = 0
- F(2) = 1
- F(n) = F(n-1) + F(n-2)
We will define a function fibonacci() that takes a number n as an argument and returns the number at position n in the Fibonacci series. This problem can be solved in multiple ways, but in the recursive solution, we can break the problem down into the following two parts:
- Base case: if n is 1, return 0 since the first term of the Fibonacci series is 0. If n is 2, return 1 since the second term of the series is 1.
- Recursive step: for all other values of n, we can calculate the number at position n by adding together the previous two terms: fibonacci(n-1) + fibonacci(n-2).
Below is the Python implementation of a recursive solution for calculating the nth number in a Fibonacci series:
def fibonacci(n):
if n == 1:
return 0
if n == 2:
return 1
return fibonacci(n-1) + fibonacci(n-2)
Example #2: Calculating the nth factorial
The factorial of the nth number is the product of all integers from 1 to n. For example, the factorial of 5 is 5! = 1 * 2 * 3 * 4 * 5 = 120. Note that the factorial of 0 is 1 and the factorial of negative numbers is undefined.
We will define a function factorial() that takes a number n as an argument and returns the factorial of n. To solve this problem using recursion, we have to break it down into the following two cases:
- Base case: if n = 0 or 1, return 1. If n < 0, return error because factorial for negative numbers is undefined.
- Recursive step: multiple n by the result of the previous term, i.e.
n * factorial(n-1).
Below is the Python implementation of a recursive solution for calculating the nth factorial:
def factorial(n):
if (n == 0 or n == 1):
return 1
if n < 0:
raise Exception("n must be positive. The factorial of a negative number is undefined.")
return n * factorial(n - 1)
Example #3: Displaying a Decimal Integer as Binary
In everyday life, the most commonly used number system is the Decimal number, which has base 10. For digital systems, the binary number system is often used and it has base 2.
One way to convert a decimal number into binary is to divide the number by 2 and record the remainder at every step, then write the remainders in reverse order (from bottom to top) and this is the binary equivalent of your integer. For example, a decimal number 36 in binary is:
36 / 2 = 18 R 0 → 18 / 2 = 9 R 0 → 9/ 2 = 4 R 1 → 4/ 2 = 2 R 0 → 2 / 2 = 1 R 0 → 1/ 2 = 0 R 1
Gathering the remainders in reverse order, we get 100100 as the binary number for the decimal number 36.
We will define a function convert_to_binary() that takes a decimal number n and returns the binary number in the form of a list of integers. To solve this problem recursively, we can break it down into two parts:
- Base case: If n is equal to 0, return a list with an integer 0. If n is equal to 1, return a list with an integer 1.
- Recursive step: Call the function
convert_to_binary()on the quotient (number n divided by 2) and keep track of the remainder from this operation.
Below is the Python implementation of a recursive function to convert decimal numbers to binary numbers:
def convert_to_binary(n):
if n == 0:
return [0]
elif n == 1:
return [1]
remainders = convert_to_binary(n // 2)
remainders.extend([n % 2])
return remainders
Conclusion
Recursion is a fundamental programming concept and is popular with coding interviews. Some common use cases for recursion are data structures with a parent-child relationship. The key to writing a recursive solution is to first define the base case and then think about the recursive step. A recursive one often results in cleaner code but it may not be as memory efficient.
Up next is Algorithms Explained #2: Sorting.
Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.