Recursion Flashcards
What is recursion?
It is a process, that involves defining a problem in terms of itself.
what are the 3 main parts of a recursive algorithm?
Base case
Working towards the base case
Recursive cal
What are some popular recursive algorithms of recursive algorithms?
-> Adding Numbers
-> The Fibonacci sequence
-> Factorial
-> Sodoku games
-> Hanoid towers
What are the advantages of recursion?
-> It makes code more readable
-> It expresses the natural mathematical aspects of a problem clearly
-> It is suitable for problems that can be broken down into smaller similar problems
-> It solves large problems by breaking them down into smaller ones
-> It can be used for mathematical modeling
What are the disadvantages of recursion?
-> They consume a lot of memory
-> They cause a stack overflow
-> Sometimes the iterative approach is more efficient than the recursion
Differentiate between direct and indirect recursion.
Direct recursion is when a function calls itself directly.
While indirect recursion is when a function calls another function that calls the original function
What is tail recursion?
This recursion in which the recursive call is the last statement executed by the function.
Differentiate between recursion and iteration.
Acronym: Come To US
Code size: Recursion has a smaller code size than iteration
Termination: Recursion terminates when the base case condition is fulfilled, while iteration terminates when the given condition fails.
Use: Recursion is used for function, iteration is used for loops
Stack memory: every recursive call requires extra stack memory, white iteration does not
What are the applications of recursion in real-world problems?
-> Tree and graph traversal
-> Sorting Algorithms
-> Divide and conquer algorithms
-> Factorial Generation
-> Memoisation
-> Backtracking algorithms