Photo by Shubham Dhage on Unsplash
Recursion with Python: A beginner guide on Recursion
For those who want to understand Recursion from its basics
Introduction to Recursion in Python
Recursion is a technique in Python (and many other programming languages) where a function calls itself one or more times to solve a problem.
It is like playing with a Russian nesting doll, each doll has a smaller doll inside it. When you open up the doll to find the smaller one inside, you keep going until you reach the smallest doll which can’t be opened. Recursion lets us tackle problems by reducing the problems to simpler ones.
Take our Russian nesting dolls all nested inside each other. Imagine we want to find out how many dolls are there in total. We would need to open each doll one by one until we got to the last one and then count how many dolls we have opened. That is recursion in action.
It is a certitude that Recursion is a powerful tool in Python because it can simplify the logic required to solve certain problems. Instead of using complicated loops or nested conditional statements, recursion can be used to elegantly break down a problem into smaller and smaller parts.
Albeit that recursion is very common in software engineering and as such can be implemented using quite a handful of different languages, this article focuses more on recursion with Python.
Definition of Recursion
Recursion is a programming technique where a function calls itself, directly or indirectly, to solve a problem. In other words, a function that uses recursion can call itself to perform a repetitive task or to solve a complex problem by breaking it down into smaller and smaller subproblems until the subproblems become simple enough to be solved directly.
From the example in the introduction, the problem is to find how many dolls are nested together, so we take on the repetitive task of opening the nested dolls until we get to the last one, then we can count the number of dolls we have. By opening the nested dolls, we broke down the task into smaller and simpler subproblems simple enough to be solved.
Why Use Recursion
The importance of recursion in programming and to programmers cannot be overstated, there are plenteous of reasons backing the use of recursion, just to mention a few
Simplifying Code: Recursion can simplify code and make it easier to understand. For example, a recursive implementation of quicksort may be shorter and clearer than an iterative implementation.
Saving Memory: Recursion can sometimes save memory because it eliminates the need to create and manage an explicit stack. Instead, the call stack is used to store intermediate results.
Avoiding Nested Loops: Recursion can sometimes be used to avoid nested loops, which can make your code harder to read and understand. Recursion cleans out unnecessary lines of code.
Recursive Thinking: Recursion can help to develop recursive thinking, which is an important problem-solving skill. It can also be used to teach concepts such as recursion and fractals to students interested.
Solving Problems with Recursive Structures: Recursion is useful for solving problems that have a recursive structure, such as traversing a tree or computing the Fibonacci sequence.
It will be noteworthy to understand that Recursion is a powerful technique for precision in programming, but it can also lead to performance issues and stack overflow errors if not used carefully. Therefore, it is important to understand how recursion works and when to use it appropriately
How Recursion Works
To use recursion in Python, a function must have two parts: a recursive case and a base case.
Recursive function calls:
A recursive function is a function that calls itself either directly or indirectly. Recursive function calls can be used to solve complex problems that involve repeating a certain operation until a specific condition is met.
Let’s take our mind to the example in the introduction about the nested Russian dolls, the main problem is to find how many dolls are nested together, so we take on a repetitive task of opening the nested dolls over and over again until we get to the last one, then we can count the number of dolls we have. By opening the nested dolls, we broke down the task into smaller and simpler subproblems simple enough to be solved and met the specific condition of getting to the last doll, counted the number of nested dolls and what do you know, problem solved.
When a recursive function is called, it creates a new instance of itself, which is executed separately. This new instance can then call another instance of itself, creating a chain of nested calls.
Take a look at the code block below, let’s say we want to print ‘hello’ multiple times, we could use a for loop but we will use recursion.
Here we define a function called greet and tell the greet function to print hello. After the function carries out the print instruction, it is then called again and again and the calls continue creating a chain of nested calls.
def greet():
print('Hello')
greet()
greet()
In a recursive function, the function will call itself with different inputs until a certain base case or termination condition is met, at which point the recursion function stops executing and then returns a result.
It's imperative to note that recursive function calls can use a lot of memory and processing power, particularly if they involve a large number of nested calls. Therefore, it's crucial to carefully design and optimize recursive algorithms to avoid excessive memory usage and long execution durations.
Base Case:
The base case in recursion is the condition that determines when the recursion should stop. It is the simplest possible problem that can be solved directly without recursion.
In a recursive function, the base case is used as a termination condition that stops the recursive process. When the base case is reached, the function returns a value or performs an action, and the recursive calls that led to it are unwound, or "popped" off the call stack.
Without a base case, the recursive function will continue to call itself indefinitely, which isn’t a very nice happenstance.
def greet():
print('Hello')
greet()
greet()
When we run the above code block, we notice that the function prints hello continuously only to terminate at some point. And that may leave you perplexed because it is expected to run infinitely.
There is an explanation for this, let’s say for some reason a programmer’s code goes into recursion without a condition to terminate it (a base case), it will run infinitely thereby causing your system to hang. So, Python being very nice provides us a limit of about one thousand recursive steps although this could vary. Please also understand that you could also change this limit to whatever you want.
To further elucidate on the base case, Imagine you are in a queue of people and you want to know how many people are in front of you and I hate queues especially the ones at Atm’s or banks, if you’re not in Africa, you most certainly cannot relate, anyway, if the queue is long it might be hard to count the people without leaving the line and losing your place.
Instead, you can ask the person in front of you how many people are in front of them. Since this person will be in the same situation as you, they will have to ask the same question to the person in front of them and so on and the sequence of asking continues until the question reaches the first person in the queue. This person can confidently reply that there is no person in front of him, so then the second person in the queue can reply one, the person behind them replies two, and so until the answer reaches you.
Now the probability that everyone in the queue will play along is extremely low but it’s a useful way to again visualize how recursion works in terms of base case.
In our earlier example on the Russian doll in the introduction, the base case would be the smallest Russian doll which is the last of the nested dolls and in this case, the base case will be the person at the front of the queue.
The Call Stack
In programming, a call stack is a mechanism used by the computer's memory to keep track of function calls during program execution.
When a function is called, the computer allocates a block of memory for that function's variables and parameters, as well as a place in the call stack to keep track of the function's execution context. The execution context includes information such as the function's return address (the point in the program where the function was called from) and the values of any local variables.
When a function completes its execution, the computer deallocates the memory used by the function's variables and parameters, and pops the function's execution context from the call stack, returning control to the function that called it.
In recursion, a function calls itself one or more times, creating a series of nested function calls. Each of these function calls is added to the call stack, creating a stack of nested function calls. When the recursion reaches its base case, the functions begin to return one by one, popping their execution contexts off the call stack until the original function call completes and the entire call stack is emptied.
Examples of Recursion in Python
Here are some of the best explaining examples of recursion in programming:
Factorial function:
The factorial of a positive integer n is the product of all positive integers up to n. The factorial function can be defined recursively as follows:
def factorial():
if n ==0:
return 1
else:
return n * factorial(n-1)
In this implementation, the base case is when n is 0 or 1 because the factorial of 0 or 1 is 1, and the function simply returns 1. The recursive case is when n is greater than 1, and the function calculates the factorial by multiplying n with the factorial of n-1.
Ackermann function:
The Ackermann function is a classic example of a computable function that is not primitive recursive. It is defined recursively as follows:
def ackermann(m, n):
if m == 0:
return n + 1
elif n == 0:
return ackermann(m-1, 1)
else:
return ackermann(m-1, ackermann(m, n-1))
The Ackermann function grows extremely quickly, and even small values of m and n can cause the function to recurse many times.
The Ackermann function takes two non-negative integer parameters, m and n. The function is defined recursively using three cases.
If m is zero, the function returns n+1. If m is greater than zero and n is zero, the function recursively calls itself with m-1 and 1.
If both m and n are greater than zero, the function recursively calls itself with m-1 and the result of a nested recursive call with m and n-1.
The Ackermann function grows extremely quickly with increasing values of m and n, and it is used as a benchmark for testing the performance of computer systems and algorithms. For example, Ackermann(4, 2) is equal to 2^65536 - 3, a number with more than 19,000 digits.
Fibonacci sequence:
The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones. The Fibonacci sequence can be defined recursively as follows:
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
This function first checks if the input value n is valid (i.e., greater than 0), and then checks for the base cases where the first two numbers in the sequence are returned. For any other value of n, the function recursively calls itself with n-1 and n-2 as arguments and returns their sum.
These are just a few examples of recursion in programming, but there are many other applications as well. Other examples include Tower of Hanoi, Binary Search etc.
In this part, I tried to stay beginner friendly with the examples on recursion, in subsequent parts, we may get more advanced with the examples, so be prepared!
Recursive Versus Iterative Solutions
Recursive and iterative solutions are two common ways to solve problems in programming. Each has its advantages and disadvantages, and the choice between the two depends on the nature of the problem and the programming language being used.
Recursive solutions use function calls to break a problem down into smaller subproblems, which are solved recursively until a base case is reached. Iterative solutions use loops to repeat a block of code until a condition is met.
Some Pros and Cons of Recursive and Iterative Solutions
Here are some pros and cons of recursive and iterative solutions:
Pros of recursive solutions:
Recursive solutions can be more elegant and easier to understand than iterative solutions, especially for problems that involve recursive definitions or patterns.
Recursive solutions can be easier to write for some problems, especially those that can be naturally expressed recursively.
Recursive solutions can be easier to debug since the recursion stack can be inspected to see where a problem occurred.
Cons of recursive solutions:
Recursive solutions can be less efficient than iterative solutions, especially for large data sets, since they require additional stack space for each recursive call.
Recursive solutions can be harder to optimize since tail recursion optimization is not supported by all programming languages.
Recursive solutions can be harder to understand for some programmers, especially those who are not familiar with recursion.
Pros of iterative solutions:
Iterative solutions can be more efficient than recursive solutions since they do not require additional stack space for each iteration.
Iterative solutions can be easier to optimize since they can be optimized using standard loop optimization techniques.
Iterative solutions can be more familiar to some programmers, especially those who are used to imperative programming languages.
Cons of iterative solutions:
Iterative solutions can be less elegant and harder to understand than recursive solutions, especially for problems that involve recursive definitions or patterns.
Iterative solutions can be harder to write for some problems, especially those that can be naturally expressed recursively.
Iterative solutions can be harder to debug since the state of the program can be more complex than in a recursive solution.
In summary, the choice between recursive and iterative solutions depends on the nature of the problem and the programming language being used. For problems that can be naturally expressed recursively, recursive solutions can be more elegant and easier to understand but may be less efficient than iterative solutions. For problems that can be naturally expressed iteratively, iterative solutions can be more efficient but may be less elegant and harder to understand than recursive solutions.
Examples of Iterative Solutions to the Above Problems
The factorial function, Fibonacci function and Binary search function can also be implemented using iterative solutions
The Factorial Function:
Factorial is a mathematical operation that calculates the product of all positive integers up to a given number. It is often defined recursively as follows: n! = n * (n-1)!
This definition can be turned into an iterative solution by using a loop to multiply the numbers from 1 to n together. Here's an example implementation in Python:
def factorial(n):
result = 1
for i in range(1, n+1):
result *= i
return result
In this implementation, we initialize a variable called result to 1, and then use a loop to multiply it by all the integers from 1 to n. The loop starts at 1 and goes up to n inclusive, so we use the range function with the arguments 1 and n+1.
At each iteration of the loop, we multiply the result by the current value of i. After the loop has been completed, we return the final value of the result, which will be equal to n!
This implementation is iterative and does not use recursion. It is more efficient than a recursive implementation in many cases, as it avoids the overhead of function calls and stack frames.
Fibonacci function:
Iterative solutions involve using loops and variables to keep track of values in the Fibonacci sequence. Here are a few examples of iterative solutions to generate the Fibonacci sequence:
1. Using a loop:
def fibonacci(n):
if n <= 0:
return "Invalid input"
elif n == 1:
return 0
elif n == 2:
return 1
else:
fib1, fib2 = 0, 1
for i in range(2, n):
fib3 = fib1 + fib2
fib1, fib2 = fib2, fib3
return fib3
2. Using a while loop: A while loop can also be used to attain the objective
def fibonacci(n):
if n <= 0:
return "Invalid input"
elif n == 1:
return 0
elif n == 2:
return 1
else:
fib1, fib2 = 0, 1
i = 2
while i < n:
fib3 = fib1 + fib2
fib1, fib2 = fib2, fib3
i += 1
return fib3
The Binary Search
Binary search is a searching algorithm that works efficiently on a sorted list of elements. It works by repeatedly dividing the search interval in half until the target element is found or the search interval is empty.
Here's an iterative implementation of binary search in Python:
```
def binary_search(arr, x):
"""
Perform binary search on a sorted list.
Parameters:
arr (list): A sorted list of elements.
x (int): The element to be searched.
Returns:
int: The index of the element if found, else -1.
"""
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
left = mid + 1
else:
right = mid - 1
return -1
Here, we initialize the left and right endpoints of the search interval as the first and last indices of the list, respectively. We repeatedly divide the interval in half by computing the middle index mid and comparing the value at mid with the target element x. If x is found, we return its index mid. If x is greater than the value at mid, we update the left endpoint of the interval to mid+1, otherwise, we update the right endpoint to mid-1. We continue the process until either the element is found or the interval is empty.
Note that this implementation assumes that the list arr is sorted in ascending order.
Pitfalls of Recursion
Common Pitfalls of Recursion
Recursion is a powerful technique in computer programming that involves a function calling itself to solve a problem. While recursion can be an elegant and efficient solution to many programming problems, it is also easy to make mistakes that can lead to incorrect or inefficient code. Here are some common pitfalls of recursion:
Infinite Recursion: This occurs when a recursive function calls itself indefinitely, without any base case to stop the recursion. This can result in the program crashing due to a stack overflow error.
Incorrect Base Case: The base case is the condition that stops the recursion. If the base case is incorrect, the recursion may not stop, resulting in infinite recursion or incorrect output.
Overlapping Subproblems: This occurs when the same subproblem is solved multiple times. This can lead to inefficiencies and slower performance.
Stack overflow: Each recursive function call adds a new frame to the call stack. If the call stack grows too large, it can result in a stack overflow error.
Performance Issues: Recursion can be slower than iterative solutions for certain problems, especially when the same subproblem is solved multiple times.
Deep Recursion: Deep recursion occurs when there are too many recursive function calls that consume a large amount of memory. This can lead to performance issues and stack overflow errors.
Unnecessary Recursion: Sometimes a problem can be solved without recursion, but a recursive function is written anyway. This can result in slower performance and unnecessary memory usage.
Incorrect Recursive Step: Recursive functions should make progress toward the base case with each recursive step. If the recursive step does not make progress, the function may never reach the base case or may result in incorrect output.
Garbage Collection: Recursive functions can generate a large amount of garbage data that must be collected by the garbage collector. This can result in slower performance and increased memory usage.
Debugging: Debugging recursive functions can be challenging, especially if there are multiple recursive calls or if the function is deeply nested. It can be difficult to understand the flow of the program and to identify the source of errors.
To avoid these pitfalls, it is important to carefully plan the design and implementation of a recursive function, make sure the base case is correct and complete, test it with different inputs, and optimize the code to avoid unnecessary recursive calls. Additionally, understanding how the recursive function interacts with the system's memory management and garbage collection processes can help avoid performance issues.
Tips and Best Practices for Recursion
How to Choose Between Recursion and Iteration
Choosing between recursion and iteration depends on the specific problem you are trying to solve, as well as the language and environment you are working with. In general, both recursion and iteration can be used to solve the same problems, but they have different advantages and disadvantages that may make one approach more suitable than the other.
Recursion involves breaking down a problem into smaller subproblems and solving each subproblem recursively until a base case is reached. Recursion can be very elegant and can lead to very concise and readable code. However, it can also be less efficient than iteration, especially if the recursion depth is very large and requires a lot of memory.
Iteration involves solving a problem by repeatedly applying a set of instructions or a loop until a specific condition is met. Iteration can be more efficient than recursion in terms of memory usage and speed, especially for problems that can be solved using a simple loop.
In general, when deciding between recursion and iteration, you should consider:
The complexity of the problem and the data structure involved.
The performance requirements of your code.
The language and environment you are working in, as some languages and platforms may handle recursion or iteration differently.
Ultimately, the choice between recursion and iteration depends on the specific problem and the trade-offs you are willing to make in terms of code readability, performance, and memory usage.
Designing and Testing Recursive Functions
When designing and testing recursive functions, it is crucial to follow a systematic approach to ensure that the function behaves as expected and that it terminates correctly. Here are some general steps that you can follow:
Identify the base case(s): These are the simplest cases that can be solved without recursion. They are the stopping criteria for the recursion.
Define the recursive case(s): These are the cases that are solved using recursion. They should be defined in terms of the same problem but with smaller input values.
Implement the function: Write the code for the recursive function using the base case(s) and recursive case(s) you identified.
Test the function: Test the function with a variety of input values, including edge cases and corner cases, to ensure that it behaves as expected.
Check for correctness: Verify that the function produces the expected output and that it terminates correctly.
Optimize the function: If necessary, optimize the function for performance or memory usage. You may be able to eliminate tail recursion or memoize intermediate results to improve performance.
Refactor the function: If necessary, refactor the function to make it more readable or maintainable. You may be able to use helper functions or data structures to simplify the code.
It is important to keep in mind that recursive functions can be more difficult to debug and optimize than iterative functions, so you should take care to write clean, well-structured code and test it thoroughly.
Recursion in Real-World Applications
Recursion is a powerful programming technique that is used in many real-world applications. Here are a few examples:
Search algorithms: Recursive search algorithms such as binary search and depth-first search are commonly used in computer science to search through data structures such as arrays, trees, and graphs. These algorithms work by breaking down the search space into smaller subproblems and solving each subproblem recursively.
Mathematical calculations: Recursion is often used in mathematical calculations, such as the Fibonacci sequence, where each term is defined in terms of the previous two terms. Recursive functions can also be used to solve complex mathematical problems such as fractals and the Towers of Hanoi.
Graphics and animation: Recursion can be used to generate complex graphics and animations, such as fractal art and 3D models. By using recursive functions to generate patterns and shapes, designers can create complex and visually interesting artwork.
Parsing and language processing: Recursive functions can be used to parse and process complex data structures such as XML and JSON. By breaking down the data into smaller subproblems and solving each subproblem recursively, programmers can extract meaningful information from the data.
Operating systems and memory management: Recursion is used extensively in operating systems and memory management systems to manage memory allocation and deallocation. Recursive functions can be used to create and manipulate data structures such as linked lists and binary trees, which are commonly used in these systems.
Recursion is a powerful and versatile programming technique that can be used in many different applications. By breaking down complex problems into smaller subproblems and solving each subproblem recursively, programmers can create elegant and efficient solutions to a wide range of problems.
Conclusion
In this robust article, we have covered a lot, hopefully, it guides and aids you in your quest to get started with Recursion.
There is a lot to learn about Recursion and albeit this article contains substantial information on Recursion I will advise you still look up other resources online to better enhance your comprehension of the subject. Here are some helpful places to look;