Recursion is a programming technique where a function calls itself to solve a problem. It is commonly used in computer science to break large problems into smaller and simpler subproblems.<\/p>\n\n\n\n
Recursion is widely used in algorithms, mathematics, searching, sorting, tree structures, and problem-solving applications.<\/p>\n\n\n\n
By the end of this training, you will be able to:<\/p>\n\n\n\n
Recursion occurs when a function repeatedly calls itself until a specific condition is met.<\/p>\n\n\n\n
A recursive function usually contains:<\/p>\n\n\n\n
The base case stops the function from calling itself endlessly, while the recursive case continues the process.<\/p>\n\n\n\n
Basic structure:<\/p>\n\n\n\n
def function_name():
if condition:
return value
else:
return function_name()<\/code><\/pre>\n\n\n\nUnderstanding the Base Case<\/h2>\n\n\n\n
The base case is the stopping condition in recursion. Without a base case, the function would continue forever and cause an error.<\/p>\n\n\n\n
Example:<\/p>\n\n\n\n
def countdown(n):
if n == 0:
print(\"Finished\")
else:
print(n)
countdown(n - 1)<\/code><\/pre>\n\n\n\nHow Recursion Works<\/h2>\n\n\n\n
When a recursive function is called:<\/p>\n\n\n\n
\n- The function executes<\/li>\n\n\n\n
- It calls itself with a smaller problem<\/li>\n\n\n\n
- Each call waits for the next call to finish<\/li>\n\n\n\n
- The process continues until the base case is reached<\/li>\n\n\n\n
- The function calls return one by one<\/li>\n<\/ol>\n\n\n\n
Example of Recursion<\/h2>\n\n\n\nFactorial Calculation<\/h3>\n\n\n\n
Factorial of 5:<\/p>\n\n\n\n
5 \u00d7 4 \u00d7 3 \u00d7 2 \u00d7 1 = 120<\/p>\n\n\n\n
Recursive solution:<\/p>\n\n\n\n
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n - 1)
print(factorial(5))<\/code><\/pre>\n\n\n\nOutput:<\/p>\n\n\n\n
120<\/code><\/pre>\n\n\n\nRecursive Countdown Example<\/h2>\n\n\n\ndef countdown(number):
if number == 0:
print(\"Done\")
else:
print(number)
countdown(number - 1)
countdown(5)<\/code><\/pre>\n\n\n\nRecursive Sum Example<\/h2>\n\n\n\ndef recursive_sum(n):
if n == 1:
return 1
return n + recursive_sum(n - 1)
print(recursive_sum(5))<\/code><\/pre>\n\n\n\nOutput:<\/p>\n\n\n\n
15<\/code><\/pre>\n\n\n\nRecursion vs Loops<\/h2>\n\n\n\nRecursion<\/h3>\n\n\n\n\n- Function calls itself<\/li>\n\n\n\n
- Easier for complex problems<\/li>\n\n\n\n
- Uses more memory<\/li>\n\n\n\n
- Cleaner code for some algorithms<\/li>\n<\/ul>\n\n\n\n
Loops<\/h3>\n\n\n\n\n- Repeats using iteration<\/li>\n\n\n\n
- Faster for simple repetition<\/li>\n\n\n\n
- Uses less memory<\/li>\n\n\n\n
- Easier for beginners<\/li>\n<\/ul>\n\n\n\n
Advantages of Recursion<\/h2>\n\n\n\n\n- Simplifies complex problems<\/li>\n\n\n\n
- Produces cleaner and shorter code<\/li>\n\n\n\n
- Useful for tree and graph structures<\/li>\n\n\n\n
- Common in divide-and-conquer algorithms<\/li>\n\n\n\n
- Helps solve mathematical problems naturally<\/li>\n<\/ul>\n\n\n\n
Disadvantages of Recursion<\/h2>\n\n\n\n\n- Can use more memory<\/li>\n\n\n\n
- Slower than loops in some cases<\/li>\n\n\n\n
- Risk of infinite recursion<\/li>\n\n\n\n
- Difficult to debug for beginners<\/li>\n<\/ul>\n\n\n\n
Common Applications of Recursion<\/h2>\n\n\n\n
Recursion is commonly used in:<\/p>\n\n\n\n
\n- Factorial calculations<\/li>\n\n\n\n
- Fibonacci sequence<\/li>\n\n\n\n
- Tree traversal<\/li>\n\n\n\n
- Searching algorithms<\/li>\n\n\n\n
- Sorting algorithms<\/li>\n\n\n\n
- File directory navigation<\/li>\n\n\n\n
- Mathematical computations<\/li>\n<\/ul>\n\n\n\n
Fibonacci Sequence Example<\/h2>\n\n\n\ndef fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(6))<\/code><\/pre>\n\n\n\nOutput:<\/p>\n\n\n\n
8<\/code><\/pre>\n\n\n\nBest Practices for Recursion<\/h2>\n\n\n\n\n- Always define a clear base case<\/li>\n\n\n\n
- Reduce the problem size in each call<\/li>\n\n\n\n
- Avoid unnecessary recursive calls<\/li>\n\n\n\n
- Test with small inputs first<\/li>\n\n\n\n
- Use recursion only when it improves clarity<\/li>\n<\/ul>\n\n\n\n
Real World Uses of Recursion<\/h2>\n\n\n\n\n- Website menu systems<\/li>\n\n\n\n
- Folder and file navigation<\/li>\n\n\n\n
- Artificial intelligence algorithms<\/li>\n\n\n\n
- Game development<\/li>\n\n\n\n
- Data structure processing<\/li>\n\n\n\n
- Search engines<\/li>\n<\/ul>\n\n\n\n
Conclusion<\/h2>\n\n\n\n
Recursion is a powerful programming technique used to solve problems by breaking them into smaller tasks. Understanding recursion improves problem-solving skills and helps developers work with advanced algorithms and data structures efficiently.<\/p>\n\n\n