RECURSION Flashcards
What is recursion
Process of solving a problem by reducing it to smaller versions of itself
What is a recursive algorithm
– Algorithm that finds the solution to a given problem by
reducing the problem to smaller versions of itself– Has one or more base cases – Implemented using recursive methods
What is a recursive method
Method that calls itself
– Every recursive call has its own• Code
• Set of parameters
• Set of local variables
What is a base case
– Case in recursive definition in which the solution is
obtained directly – Stops the recursion
What is a general solution
– Breaks problem into smaller versions of itself
What is a general case
– Case in recursive definition in which a smaller
version of itself is called – Must eventually be reduced to a base case
What is the difference between a directly recursive method and an indirectly recursive method
• Directly recursive: a method that calls itself • Indirectly recursive: a method that calls
another method and eventually results in the
original method call. Method Acalls method B, which in turn calls method A.
What is infinite recursion
– Recursive calls are continuously made until memory has been exhausted – Caused by either omitting base case or writing recursion step that
does not converge on base case – This error is analogous to the problem of an infinite loop in an
iterative (nonrecursive) solution.
Describe the progression after a recursive call is completed
• After completing a recursive call – Control goes back to the calling environment – Recursive call must execute completely before
control goes back to previous call – Execution in previous call begins from point
immediately following recursive call
What are the differences between recursion and iteration
- Control statement:
Recursion: selection; Iteration: repetition(loops)
2.Termination test:
– Iteration terminates when the loop-continuation condition fails– Recursion terminates when a base case is reached
3.recursion is a process, always applied to a function and iteration is applied to the set of instructions which we want to get repeatedly executed.
*See notes for code that can be executed both recursively and iteratively
Why is a recursive approach preferred over an iterative approach
• A recursive approach is normally preferred over an iterative
approach when the recursive approach more naturally
mirrors the problem and results in a program that is easier
to understand and debug. • A recursive approach can often be implemented with fewer
lines of code. • Another reason to choose a recursive approach is that an
iterative one might not be apparent.
One of the main disadvantages of recursive solutions is that they may take more memory space as compared to iterative solutions. Using relevant examples, identify and explain scenarios / situations, where it is prudent to use a recursive solution.
1.If time complexity is the point of focus, and number of recursive calls would be large, it is better to use iteration. However, if time complexity is not an issue and shortness of code is, recursion would be the way to go.
2) Faster to code.
3) Easy to handle all the edge cases. Because edge cases are the base cases in recursion.
4) Easier to read and understand.
Give two reasons why we need the if statement in recursive code
To prevent infinite recursion
Identifies general cases
What are the disadvantages of recursion
Recursion uses more memory. Because the function has to add to the stack with each recursive call and keep the values there until the call is finished, the memory allocation is greater than that of an iterative function.
Recursion can be slow. If not implemented correctly (as stated above with memoization) it can be much slower than iteration.
