Recursive and Iterative Approach

Recursive Approach:

Recursion is a method where a function calls itself in order to solve a problem. The function continues to call itself until it reaches a base case, at which point it stops and returns a result. Recursive solutions can be more elegant and concise, but they can also be less efficient as they may require more memory to keep track of multiple instances of the same function. Lets see Recursive method to implement Fibonacci Series.

def fib(n):

    if n <= 2:

        return 1

    return fib(n-1) + fib(n-2)

• Time Complexity - O(2ⁿ) [2 to n-th power]

• Space Complexity - O(n)

Iterative Approach:

Iteration, on the other hand, is a method where a problem is solved by repeatedly executing a block of code until a certain condition is met. This is typically done using a loop, such as a for or while loop. Iterative solutions can be more efficient as they do not require as much memory, but they may not be as easy to understand or maintain as recursive solutions.

def fib(n):

    curr, prev = 1,0

    if n<=0:

        return 0

    if n==1:

        return 0

    if n==2:

        return 1

    while (n-1):

        curr , prev = curr + prev , curr

        n-=1

    return curr

• Time Complexity - O(n) 

• Space Complexity - O(1)

When to use Recursive:

Both recursion and iteration can be used to solve the same problem, and the choice between the two often depends on the specific requirements of the problem and the preferences of the programmer. 

Recursion is made for solving problems that can be broken down into smaller, repetitive problems. It is especially good for working on things that have many possible branches and are too complex for an iterative approach. 

Any task which can be accomplished by recursion can also be done by iterative code. However, Iterative code is very easy to implement. But sometimes recursion is the easy way to write the program.

Risks in Recursive

Recursion involved a number of function calls. One should keep in mind that function calls involve system stack and each call is associated with creation of a stack frame. So if the number of calls are high it can result in exhaustion of the memory which is not acceptable.

So in most of the cases iterative code is favorable. 

Recursion should only be used where the maximum expected call can be supported by the system stack or when the primary memory size is huge.

In case you forget, You’re doing a good job. Keep pushing yourself.