Recursion in Python

Recursive functions are functions that call themselves. Recursion is often used in ways similar to iteration, and many calculations can often be computed using either process. However, iteration and recursion have their own pros and cons that can vary depending on the calculation being computed.

Recursion vs Iteration

Let's talk about factorial, the factorial of a non-negative integer n (denoted by n! ) is the product of all positive integers less than or equal to n.

$$n!=n\times n-1\times n-2\times n-3.....\times1$$

The iterative solution uses for and while loops leading to iterative algorithms.

def factorial(n):
    prod=1 
    for i in range(1,n+1):
        prod*=i
    return prod

Iterative algorithms are efficient from computer's POV.

Recursive solution

Reduces the problem to a simpler/smaller version of same problem.
A base case is used keep reducing problem until reach a simple case that can be solved directly. A base case ****to avoid ending up in an infinite loop from calling itself too many times.

def factorial(n):
    if n==1:
        #base_case
        return 1
    else:
        #recursive_step
        return n*factorial(n-1)

So in essence, recursion systematically reduces a problem (into a smaller or simpler version of that problem) until it can be solved directly and then successively returns the calculated values to the functions that called for them (in this case, factorial reduced the problem to a series of simple multiplications) until a final solution is returned.

Recursive solution may be simpler, more intuitive and recursion may be efficient from programmer's POV.

Mathematical Induction

How to know one recursive code will work? For that we can use mathematical tool, mathematical induction.

Using mathematical induction to prove a statement indexed on integers is true for all values of n:

Prove it is true when n is smallest value (e.g. n = 0 or n = 1)
Then prove that if it is true for an arbitrary value of n, one can show that it must be true for n+1

EXAMPLE : Proof the following

$$1 + 2 + 3 + ….. + n = n(n +1)/2$$

$$ \text{Let } n=1 $$

$$LHS = 1 \text{ and } RHS = 1 (1+1)/2 = 1 \text{ , so the statement is true for n =1 }$$

$$\text{Let us consider the statement to be true for}$$

$$ n=k \text{ then } 1 + 2 + 3 + …. + k = k (k+1)/2 $$

$$\text{For } n=k+1$$

$$ (1 + 2 + 3 + … + k) + (k + 1) = k(k + 1)/2 + (k + 1)$$

$$ \text{Hence we prove statement is true for}$$

$$ n=k+1$$

Let’s see a code for sum of natural numbers using iteration and recursion.

Iteration

def snat(n):
    result = 0 
    for num in range(1,n+1):
        result=result+num
    return result

Recursion

def snat(n):
    if n==1:
        #basecase
        return 1
    else:
        #recursivecase
        return n+snat(n-1)

We can use the same logic for recursive code

We will take the smallest value as base case which will be true for statement. For recursive case we can assume that it will return true value for rest cases.

Recursion with Multiple Base Cases

The Fibonacci numbers are the numbers in the following integer sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation

$$F_{n} = F_{n-1} + F_{n-2}$$

with seed values

$$F_{0} = 0 \hspace{0.1cm} and \hspace{0.1cm} F_{1}=1$$

def fib(x):
    if x==1 or x==0:
        #two base cases
        return 1
    else:
        # recursive case
        return fib(x-1)+fib(x-2)

Palindrome of Strings

Then we will solve problem recursively.
- Base case will be the length of string is 0 and 1 is palindrome
- recursive case will be first character matches last character, then is a palindrome if middle section is a palindrome.
  - for example

        isPalindrome("madam") is same as:
        "m"=="m" and isPalindrome("ada")

        def isPalindrome(s):

            def toChars(s):
               #converts string to characters
                s = s.lower()
                ans = ''
                for c in s:
                    if c in 'abcdefghijklmnopqrstuvwxyz':
                        ans = ans + c
                return ans

            def isPal(s):

                if len(s) <= 1:
                    #base case
                    return True
                else:
                    #recursive case
                    return s[0] == s[-1] and isPal(s[1:-1])

            return isPal(toChars(s))

Similarly we can check if some number is palindrome or not.

We would have to convert num into strings as numbers are not iterable.
Unlike in strings we don’t have to worry about punctuations as it is a number. We will directly check for palindrome in program.
- Base case if length of a number is 1 then it is palindrome
- Recursive case will be first character matches last character, then is a palindrome if middle section is a palindrome.

            isPalindrome(11011) is same as:
            "1"=="1" and isPalindrome(101)

            def isPalindrome(num):

                def isPal(s):
                    if len(s) == 1:
                        return True
                    else:
                        return s[0] == s[-1] and isPal(s[1:-1])

                s=str(num)

                return isPal(s)

Recursion in Python

Table of contents

Recursion vs Iteration

Mathematical Induction

Recursion with Multiple Base Cases

Palindrome of Strings