Recursion in Python
- Is one of the most powerful tools in a programming language.
- It is defined as defining anything in turns of itself.
- It is used to solved problems involving iteration(multiple education), in reverse order. Iteration loop statements, helps a programmer to carry out certain task a known times or as long as the desired condition is true.
- If a function refers itself, i. e. call itself, it is said to be a recursive function.
- A function contain either a call statement to itself or a call statement to a second function, which again call back, the original function.
- The first type is known as direct recursion and second type is known as indirect recursion.
For a function to be recursive, it must have the following two properties:
- There must be a base criteria for with the function does not call itself.
- Each time a function calls itself, must be closer to the base criteria.
- The function with this two properties is set to be a well define function.
- When a function calls itself recursively, it is known as recursion.
Types of recursion:
- Recursion are of four types.
- Direct Recursion
- Indirect Recursion
- Tail Recursion
- Non-Tail Recursion
- The recursion in which the function calls itself is called direct recursion. In this type, only one function is involved.
- The recursion in which two function calls each other is known as indirect recursion.
- A Recursive function is called tail recursive if recursive is the last thing done by function,there is no need to keep record of previous state.
- A recursive function is called non-tail recursive if recursive is not the last thing done by function ,there is no need to keep record of previous state.
Advantages of recursion
- Recursion provides logical simplicity to an iterative statement .
- It also provide self documentation of recursive programme.
- It made the code look more simpler and effective.
- Complex function can be further split into various smaller sub-problems .
Drawback’s of Recursion
- A recursive solution to a problem is more expensive than a non-recursive solution.
- Recursive solution takes more time and also occupies greater memory space.
- More space is reallocated.
- Debugging is very difficult.
Implementation of recursion
In general, there are two approaches to writing repetitive algorithms. One is with use of iteration. The other uses recursion.
Suppose P is a procedure containing either a call statement to itself or a call statement to a second procedure that may eventually result in a call statement back to the original procedure P. Then, P is called recursive procedure. So, program will not continue to run indefinitely, a recursive procedure must have following two properties:
- There must be certain criteria, called base criteria for which procedure does not call itself.
- Each time the procedure does call itself, it must be closer to base criteria.
- A function is said to be recursively defined if function definition refers to itself. It must have following two properties:
- There must be certain arguments , called base values, for which function does not refer to itself.
- Each time function does refer to itself, the argument of function must be closer to base value.
Product of positive integers from 1 to n, inclusive is called “ n factorial” and is denoted by n! .
n! =1.2.3… .. .. (n-1) (n-1) n
0! =1, 1! =1, 2! =1.2=2, 3! =1.2.3=6, 4! =22.214.171.124=24
print("enter positive number")
print("factoial of 0 is 1")
print("factorial of ",num," ",end=" ")
Factorial of 4 =24
The celebrated Fibonacci sequence is 0,1,1,2,3,5,8,13,24,34,55…….
That is f0=0 and f1=1 and each succeding term is sum of two preceding terms, the next two terms of sequence are:
34+55=89 and 55+89=144
if n_terms <=0:
print("enter positive value")
for i in range(n_terms):