data-structures/algorithms/recursion/THEORY.md

Recursion

Definition:

• In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. source
• Most of the modern programming languages allow recursion by allowing the function to call itself within its own code.

Fundamentals:

• Base Case:

  • The recursive function must have a base condition to terminate itself or the function shall end up in an infinite loop.

  • For example

    def factorial(number):
    return number * factorial (number - 1)
    

    • Here, there is no condition to end the recursive call. Hence, the function will run infinitely until the its terminated.

    • This could be extremely dangerous as a non-terminating recursive program can lead to system crash.

    • Hence, a base case plays an extremely important role for recursive algorithms.

    • An example of a recursive function with a base condition:

      def factorial(number):
      if number in (0, 1):
          return 1
      else:
          return number * factorial(number - 1)
      

  • Here, the function will stop its recursive call when the base condition is reached, hence terminating itself.

• Time Complexity:

  • Time complexity of recursive algorithms depends on the following factors:
  • Total number of recursive calls
    • A recursive function of input N that is called N times will have a runtime of O(N).
  • Time complexity of additional operations for each recursive call.

• Interaction with computer memory:

• • When a function is called, its memory is allocated on a stack. Stacks in computing architectures are the regions of memory where data is added or removed in a last-in-first-out (LIFO) process. Each program has a reserved region of memory referred to as its stack. When a function executes, it adds its state data to the top of the stack. When the function exits, this data is removed from the stack. Source.

More about recursion and its applications