Recursion in Python
Dr M Chandralekha
Assistant Professor (Sr. Grade)
Dept. of CSE, AVV, Chennai
Recursion in Python
• Recursion is a programming technique where a function calls itself
either directly or indirectly to solve a problem by breaking it into
smaller, simpler subproblems.
• In Python, recursion is especially useful for problems that can be
divided into identical smaller tasks, such as mathematical
calculations, tree traversals or divide-and-conquer algorithms.
Working of Recursion
• A recursive function is just like any other Python function except that
it calls itself in its body.
• Let's see basic structure of recursive function:
Recursive function contains two key parts:
Base Case: The stopping condition that prevents infinite recursion.
Recursive Case: The part of the function where it calls itself with
modified parameters (Function calls itself with smaller input).
Example 1: Factorial Calculation
This code defines a recursive function to calculate factorial of a
number, where function repeatedly calls itself with smaller values until
it reaches the base case.
Example 2: Fibonacci Sequence
• This code defines a recursive function to calculate nth Fibonacci
number, where each number is the sum of the two preceding ones,
starting from 0 and 1.
This function follows the Fibonacci sequence rule:
F(n) = F(n−1) + F(n−2)
with:
F(0) = 0
F(1) = 1
These are the stopping points — the recursion stops expanding here.
That means:
Explanation F(5)
Practice Questions
1. Write a recursive function that takes a positive integer and returns the
sum of its digits. For example, sum_of_digits (1234) should return 10
2. Write a recursive function to calculate the power of a number. Given
two integers x and n, compute x^n (x raised to the power of n)
3. Write a recursive function to check if a given string is a palindrome
(reads the same forwards and backwards). For example, "madam" is a
palindrome
4. Write a recursive function to reverse a string. For example,
reverse("hello") should return "olleh".
5. Write a recursive function that counts the number of vowels (a, e, i, o,
u) in a given string
Thank You