Skip to content

Latest commit

 

History

History
 
 

Recursion

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 

Recursion

Any function which calls itself is called recursive. A recursive method solves a problem by calling a copy of itself to work on a smaller problem. This is called the recursion step. The recursion step can result in many more such recursive calls. It is important to ensure that the recursion terminates. Each time the function calls itself with a slightly simpler version of the original problem. The sequence of smaller problems must eventually converge on the base case.

  • Recursive algorithms have two types of cases, recursive cases and base cases.
  • Every recursive function case must terminate at a base case.
  • Generally, iterative solutions are more efficient than recursive solutions [due to the overhead of function calls].
  • A recursive algorithm can be implemented without recursive function calls using a stack, but it’s usually more trouble than its worth. That means any problem that can be solved recursively can also be solved iteratively.
  • For some problems, there are no obvious iterative algorithms.
  • Some problems are best suited for recursive solutions while others are not.

Questions :

  • Factorial ----> C++ | Java
  • Fibonocci ----> C++
  • Kth_Symbol_Grammar ----> C++
  • Phone Keypad ----> C++
  • Tower of Hanoi ----> C++ | [Java] (/Code/Java/Tower_of_Hanoi.java)
  • Generate all valid parantheses ----> Java