CODEWITHSUNDEEP
algorithm
Brian
Brian

Reputation: 151

Is recursion a loop

"1. The program will calculate the values using repetitive execution (loops)."

Recursion is repetitive execution but, i do not think it's a loop, do you think if I used recursion it would follow the guideline above?

Upvotes: 2

Views: 135

Answers (2)

Chris Taylor
Chris Taylor

Reputation: 47392

Loops are fundamentally about iteration, which is different to recursion. The main difference is that an iteration uses a constant amount of space, whereas recursion uses more space the deeper the recursion goes. For example, here are iterative and recursive procedures to compute the sum of the numbers from 1 to n

def sum_iter(n):
  x = 0
  for i in range(1,n+1):
    x += i
  return x

def sum_recursive(n):
  if n == 0:
    return 0
  else:
    return n + sum_recursive(n-1)

If you run these with a very large argument, you will run out of stack space (a "stack overflow") on the recursive version, but the iterative version will work fine.

There is a special kind of recursion called tail recursion, which is where the function doesn't have to do anything with the value from a recursive call except pass it to the caller. In this case you don't need to keep track of the stack - you can just jump straight to the top. This is called tail call optimization. A tail recursive function to calculate the sum of the integers 1 to n looks like

def sum_tailrec(n):
  def helper(s,i):
    if i == 0:
      return s
    else:
      return helper(s+i, i-1)
  return helper(0, n)

In this case people often refer to the function helper as an iterative recursion, because (with tail call optimization) it is only using a constant amount of space.

This is all a bit moot, because Python doesn't have tail call optimization, but some languages do.

Upvotes: 1

Michael Petrotta
Michael Petrotta

Reputation: 60902

No. In fact, it looks like the assignment is specifically asking for the "opposite" of recursion, iteration.

Upvotes: 3

Related Questions