Python Programming – Recursion

Python Programming – Recursion

Alike C/C++, a function can call itself, rather than from any other function. This concept is termed recursion. Recursive functions act like loops that they iterate within the function to perform some operation. The programmer must consider some points while using recursion, which are

• Recursion can be used for any function involving loops.
• While developing programs using recursion, the programmer must follow some guidelines, such as

1. There must be a key variable, which will be responsible for the termination of recursion,
2. To determine the base value, which the key variable has to meet to reach the termination,
3. To make sure the key variable must approach the base value in every recursive call.
4. To make the recursive function terminate when the key variable reaches the base value.

The programming example to compute the factorial of a given number using recursion is presented in Code: 6.14. In this program, initially, the function call fact(num) is made with the number input by the user. In the function definition, recursive calls are made to function fact() with the value of n is decrementing by 1 in every recursive call. This process continues until the value of n becomes 1. Then, the function fact() computes the factorial by returning the values recursively. Fig.6.2. displays the computation of recursive factorial function.

• Python Programming – Date and Time Functions
• Python Programming – Python Functions
• Python Programming – Python User Defined Functions

Code: 6.14. Program to compute factorial of a number using recursion.

# This program computes the factorial of a number using recursion #function definition def fact(n): ‘computes factorial using recursion’ if(n==0): retum(1) else: retum(n* fact(n-1)) # Function call num=input(‘enter a number:’) num=int(num) result=fact(num) print(‘factorial=’,result)

Output enter a number:6 factorial=720

fact(6)                                         # 1st call with 6 6 * fact(5)                                   # 2nd call with 5 6*5*fact(4)                                # 3rd call with 4 6*5*4*fact(3)                          # 4th call with 3 6*5*4*3*fact(2)                      # 5th call with 2 6*5*4*3*2*fact(l)                  # 6th call with 1 6*5*4*3*2*1                         # return from 6th call with value 1 6*5*4*3*2                              # return from 5th call 6*5*4*6                                   # return from 4* call 6*5*24                                   # return from 3rd call 6*120                                     # return from 2nd call 720                                         # return from 1st call

Advantages of Recursion

• Recursive functions divide the problem into smaller similar fragments and then computes them.
• The recursive code looks precise and cleaner as compared to using loops.
• Sequence generation is simpler in recursion such as Fibonacci series as compared to that of loops.

Disadvantages of Recursion

• Recursive code is hard to develop and debug as it involves huge complexity.
• Difficult to understand.
• Recursive functions are expensive as numerous calls occur within the function, which takes up a lot of memory space and time.
• Recursive functions are slower than iterations (loops).

Python Tutorial