Explain the concept of recursion and provide an example of a recursive algorithm.

Question

Aryan Kumar · Answer

Sure. Recursion is a programming technique where a function calls itself. This can be used to solve problems that would be difficult or impossible to solve with a loop.

Here is an example of a recursive algorithm that prints the Fibonacci sequence:

Python

def fib(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

The fib() function works by breaking down the problem of finding the nth Fibonacci number into two smaller problems: finding the (n - 1)th Fibonacci number and finding the (n - 2)th Fibonacci number. The fib() function then solves the smaller problems and then adds the two solutions together to get the solution to the original problem.

Here is an example of how the fib() function would be used to print the first 10 Fibonacci numbers:

Python

for i in range(10):
    print(fib(i))

This code would print the following output:

Code snippet

forum

Explain the concept of recursion and provide an example of a recursive algorithm.

Can you answer this question?

1 Answers