A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • 5 years ago

Iterative and recursive seem to be the same. Can anyone explain to me, in layman's terms, the difference? Thx.

  • This Question is Closed
  1. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    A recursive function is a function that calls itself with smaller versions of the original problem until it's in the base case. An iterative program does not call itself.

  2. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I tried the plain English way, but this might work better, at the risk of being more confusing. Honestly, the way I think about it is that whenever I see a function calling itself, I imagine a trapdoor. So in the line: else: return fib(x-1) + fib(x-2) I read as far as else: return fib(x-1) and then I think, OK, the current function stops, and (x-1) falls through to fib(x). Until that's completed, the rest of this function is on hold. That could happen hundreds of times, but as long as x isn't in the base case, it's going to keep falling through that trapdoor into smaller and smaller problems. It might help to use the fibonacci example in the lecture, but expand it to show the flow of control. def fib(x): """Return fibonacci of x, where x is a non-negative int""" if x == 0 or x == 1: return 1 else: return fib(x-1) + fib(x-2) So say we call it with 3 as an argument: 1. if x==0 or x==1: return 1 ##Nope 2. else: return fib(x-1) +fib(x-2) a) call fib with 2 as an argument. This is fib(x-1) in line 2. b) If x ==0 or x ==1: return 1 ##nope c) else: return fib(x-1) + fib(x-2) i) call fib with 1 as an argument.This is fib(x-1) in line c. ii) If x ==0 or x ==1: return 1 ##Yes! we can do this! the fib(x-1) in line c = 1 iii) call fib with 0 as an argument. This is fib(x-2) in line c. iv) If x ==0 or x ==1: return 1 ##Yes! we can do this! the fib(x-2) in line c = 1 c) is now completed. Returns 2 as fib(x-1) in line 2 d) call fib with 1 as an argument. This is fib(x-2) in line 2. i) If x ==0 or x ==1: return 1 ##Yes! we can do this! the fib(x-2) in line 2 == 1 2. is now completed. fib(x-1) = 2, fib (x-2) = 1, so line 2 returns 3.

  3. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Thanks a million! I think I got it - for example - and feel free to correct this: def recur(x): if x == 0: print "This is finally the end of the recursive loop with value x:", x else: print x, "Where x = x - 1:", (x-1) return recur(x-1) I think this is a good example for beginners to understand what happens...and your layman's term explained it nicely. For anything else more complicated than this...I may be at a loss! ;-)

  4. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Exactly. This has also been pretty hard for me to get my head around. I've found that with recursive functions it's important for me to keep in mind what they're actually returning and where they're returning it. In the case of fibonacci, that function is getting an integer whenever it says something like fib(x-1). So if I wanted to understand it without getting that snake-eating-its-own-tail confused feeling, I might think of it as: if x == 0 or x == 1: return 1 else: return [INTEGER] + [INTEGER] and worry about the recursive calls later. it helps me separate the number of recursions from the number of answers being returned (at each level, The number of recursions is based on the size of the initial value--fib(21) recurs way more times than fib(2). But no matter how big the initial value is, you're only ever going to get an integer back from any single function call.

  5. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Sorry, should be: It helps me separate the number of recursions from the number of answers being returned.

  6. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Thanks somnamniac - you've been quite the help. I'll be going over the recursion lectures anyways...they'll make more sense now.

  7. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.