Recursion

• Recursion is a Self-referential situation. In programming, recursion means calling a function in itself

• In general, most of the problems can be solved without recursion

• The recursive solutions are likely to be much cleaner and concise

• Decision on when to use recursion

  • For some problems, a recursive solution, though possible, will be awkward rather than elegant.

  • Recursive implementations often consume more memory than non-recursive ones.

  • In some cases, using recursion may result in a slower execution time

Recursion in Python

Namespace

• When we call a function in python, the interpreter creates a new local namespace, which avoids variable collision with the variables defined somewhere else in the code

• The interpreter also creates a separate local namespace for each instance of the function

• The recursion function in python has a limit (of 1000 calls) on the number of times it can call itself

• Maintaining State

  When dealing with recursive functions, keep in mind that each recursive call has its own execution context, so to maintain state during recursion you have to either:

  • Thread the state through each recursive call so that the current state is part of the current call’s execution context

  • Keep the state in the global scope

Base Case

• The recursion function must have the following things

  • There are base cases that are directly solvable without the need for further recursion.

  • Each recursive call moves the solution progressively closer to a base case

Call Stack

Pros and Cons of Recursion

Recursion vs Iteration

• Recursion results are in similar behavior to for or while loops

  • except recursion progresses closer to a target condition

  • while for loops run a set number of times

  • while loops run until a condition is no longer met.

• Recursion is declarative because you set the state you want to reach and for/while loops are iterative because you have to set the number of repetitions

Recursion Implementation

• Find sum from 1 to n

• Find Factorial using Recursion

• Fibonacci series using Recursion

• Binary search implementation

• Reverse a LinkedList using recursion

• Detect a Palindrome

  • A palindrome is a word that reads the same backward as it does forward. Examples include Racecar, Level, Kayak, Reviver, Civic, etc.

• Balanced parentheses question using recursion

• Convert tree to a doubly LinkedList using recursion

• Reverse a stack using recursion

• Tree traversal (For simplicity list within a list traversal)

• Quicksort implementation

• Merge sort implementation

References for Further Reading

Recursion in Python Tutorialwww.educative.io

How does recursion work in programmingwww.educative.io

Recursion in Python: An Introduction – Real Pythonrealpython

Recursion: Practice ProblemsMedium