Recursion

Recursive programming is a procedure in which a method calls itself, so that a problem is solved more and more with each method call. This continues until the problem is reduced to a very simple case.

Some tasks in computer science can be solved well by reducing a large problem step by step to smaller and smaller problems of the same kind until simple (trivial) solutions arise . From this finally the solution of the original large problem is put together.

Syntax

def function_name(parameters):
    # code to be executed
    return function_name(parameters)

Example: factorial

def factorial(number):
    if number < 2:
        return 1
    else:
        return number * factorial(number - 1)

print("factorial of 8 is " + repr(factorial(8)))

Output

factorial of 8 is 40320

Code Explanation

This code defines a function factorial that calculates the factorial of a number using recursion. The factorial of a number is the product of all positive integers less than or equal to that number.

The function first checks if the input number number is less than 2. If it is, the function returns 1, which is the base case for the recursion. If the input number is greater than or equal to 2, the function returns the product of the input number and the factorial of the previous number (i.e. number - 1). This process continues until the base case is reached and the recursive calls return the results back up the chain, giving the final result.

Finally, the code calls the factorial function with the argument 8 and prints the result. The output should be “factorial of 8 is 40320”.

Example: fibonacci

def fibonacciAlgorithm(number):
    if number == 0 or number == 1:
        return number
    else:
        return fibonacciAlgorithm(number - 1) + fibonacciAlgorithm(number - 2)

print("fibonacci number of the number 10 is " + repr(fibonacciAlgorithm(10)))

Output

fibonacci number of the number 10 is 55

Code Explanation

The code defines a function fibonacciAlgorithm that computes the n-th Fibonacci number where n is the input parameter number. The Fibonacci sequence is a sequence of numbers in which each number is the sum of the two preceding ones, starting from 0 and 1.

The function first checks if the input number is 0 or 1 and returns the number itself. If not, it returns the sum of the n-1-th and n-2-th Fibonacci numbers, which are calculated recursively.

Finally, the code calls the fibonacciAlgorithm function with the argument 10 and prints the result.