Online Training
Q4 2024
Nov 19 to Dec 10
11.00 AM EST: USA, UK, Canada, Mexico and Europe
06.00 AM GMT: MiddleEast, Asia and Australia
A base case in recursion is a condition that stops the function from calling itself indefinitely. It’s essential to have a base case to prevent endless loops.
# Base Case Example
def countdown(value):
if value == 0:
print("Done")
else:
print(value)
countdown(value - 1)
The recursive step is where the function calls itself with a modified input that gradually approaches the base case. This step ensures that the function eventually reaches the base case.
# Recursive Step Example
def countdown(value):
if value <= 0:
print("Done")
else:
print(value)
countdown(value - 1) # Recursive step
Recursion is a method where a problem is solved by breaking it down into smaller instances of the same problem. A recursive function has a base case and a recursive step.
A call stack is a data structure used by programming languages to keep track of function calls. Each function call is added to the stack, and when a function completes, it is removed from the stack.
Big-O runtime measures how the execution time of a recursive function grows with the size of the input. For instance, if a function makes N calls, its runtime is O(N). If it calls itself twice per call, its runtime is O(2^N).
A weak base case does not adequately stop the recursion, leading to infinite loops and potential stack overflow errors.
Execution context refers to the set of information (like variables) maintained by the programming language during each recursive call.
A stack overflow error occurs when a recursive function uses too many resources. This often happens when the recursion goes too deep.
# Example causing Stack Overflow
def myfunction(n):
if n == 0:
return n
else:
return myfunction(n - 1)
myfunction(1000) # This will cause a stack overflow error
A Fibonacci sequence is a series where each number is the sum of the two preceding ones. Recursive functions can be used to calculate Fibonacci numbers, but can be inefficient for large inputs.
# Fibonacci Sequence Example
Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
You can simulate a call stack using a while loop to keep track of function calls and their states, helping to understand recursion better.
# Call Stack Example
5
/ \
/ \
3 8
/ \ / \
2 4 7 9
A binary search tree (BST) is a data structure where each node has at most two children, used for efficient data retrieval. Recursion can be used to build and manage BSTs.
# Building BST Example
def build_bst(my_list):
if len(my_list) == 0:
return "No Child"
middle_index = len(my_list) // 2
middle_value = my_list[middle_index]
tree_node = {"data": middle_value}
tree_node["left_child"] = build_bst(my_list[:middle_index])
tree_node["right_child"] = build_bst(my_list[middle_index + 1:])
return tree_node
sorted_list = [12, 13, 14, 15, 16]
binary_search_tree = build_bst(sorted_list)
print(binary_search_tree)
You can use recursion to flatten nested lists into a single list. The function checks if an element is a list itself and recursively processes it.
# Flatten Nested List Example
def flatten(mylist):
flatlist = []
for element in mylist:
if type(element) == list:
flatlist += flatten(element)
else:
flatlist.append(element)
return flatlist
print(flatten(['a', ['b', ['c', ['d']], 'e'], 'f']))
# Output: ['a', 'b', 'c', 'd', 'e', 'f']
The Fibonacci sequence can be computed recursively by summing the two previous numbers in the sequence. The function has a base case and recursive calls.
# Fibonacci Example
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(5)) # Output: 5
To find the depth of a binary tree, a recursive function is used to calculate the depth of each subtree and return the maximum depth.
# Tree Depth Example
def depth(tree):
if not tree:
return 0
left_depth = depth(tree["left_child"])
right_depth = depth(tree["right_child"])
return max(left_depth, right_depth) + 1
To sum the digits of a number recursively, the function breaks down the number into its digits and adds them up.
# Sum Digits Example
def sum_digits(n):
if n <= 9:
return n
last_digit = n % 10
return sum_digits(n // 10) + last_digit
print(sum_digits(552)) # Output: 12
A palindrome is a word that reads the same forwards and backwards. A recursive function checks if the first and last characters match and then recursively checks the remaining substring.
# Palindrome Example
def is_palindrome(s):
if len(s) < 2:
return True
if s[0] != s[-1]:
return False
return is_palindrome(s[1:-1])
print(is_palindrome('racecar')) # Output: True
An iterative approach to calculating Fibonacci numbers is often more efficient than a recursive one for large inputs.
# Iterative Fibonacci Example
def fibonacci(n):
if n < 0:
raise ValueError("Input must be 0 or greater!")
fiblist = [0, 1]
for i in range(2, n + 1):
fiblist.append(fiblist[i - 1] + fiblist[i - 2])
return fiblist[n]
print(fibonacci(5)) # Output: 5
Recursive multiplication can be used to repeatedly add numbers. It works by breaking the multiplication into smaller parts.
# Recursive Multiplication Example
0, 1, 1, 2, 3, 5, 8, 13, 21, ...
While recursion can be elegant and simple, it can affect performance due to function call overhead and memory usage.
Favourites
Monitor your IT infrastructure effortlessly with Site24x7 and get comprehensive insights and ensure smooth operations with 24/7 monitoring.
Sign up now
Welcome to our comprehensive collection of programming language cheatsheets! Whether you're a seasoned developer or a beginner, these quick reference guides provide essential tips and key information for all major languages. They focus on core concepts, commands, and functions—designed to enhance your efficiency and productivity.
ManageEngine Site24x7, a leading IT monitoring and observability platform, is committed to equipping developers and IT professionals with the tools and insights needed to excel in their fields.
Monitor your IT infrastructure effortlessly with Site24x7 and get comprehensive insights and ensure smooth operations with 24/7 monitoring.
Sign up now!
Java
HTML and CSS 
Python
Javascript
Troubleshooting
Blogs
Learn
Tools