Return to Video

Recursive Vs Iterative - Intro to Computer Science

  • 0:01 - 0:04
    So any procedure that we could write recursively. We're going to
  • 0:04 - 0:07
    also write without using a recursive definition. And I want to
  • 0:07 - 0:10
    show you another way that we might have defined is
  • 0:10 - 0:13
    palindrome. So here we're doing this with the for loop,
  • 0:13 - 0:16
    and we're looping using the variable i and the range
  • 0:16 - 0:19
    from 0 to the length of s divided by 2.
  • 0:19 - 0:24
    So that's going through halfway of s. And inside the
  • 0:24 - 0:26
    loop we have an if-test that checks if they character
  • 0:26 - 0:31
    at position i is different at the position negative i
  • 0:31 - 0:33
    plus 1. So that's going to be counting from the back
  • 0:33 - 0:37
    of the string, i's positions away. If those are different,
  • 0:37 - 0:40
    then we've found a mismatch and we return false. If they're
  • 0:40 - 0:43
    not different, we're going to keep going through the loop. Once
  • 0:43 - 0:44
    we get to the end of the loop without finding any
  • 0:44 - 0:48
    differences, we know it's a palindrome and we return true.
  • 0:48 - 0:52
    So this is also another way we could define is palindrome.
  • 0:52 - 0:54
    I think this is more complicated to understand, and harder to
  • 0:54 - 0:58
    get right. It took me three tries before this code worked correctly,
  • 0:58 - 1:02
    whereas the recursive definition, I could get right the first time.
  • 1:02 - 1:05
    If we wanted to test very long palindromes, this would be much
  • 1:05 - 1:08
    more efficient, than the code that we had with the recursive
  • 1:08 - 1:11
    definition. And there are a couple of reasons for that. One is
  • 1:11 - 1:14
    that the recursive definition keeps making new strings, every time we
  • 1:14 - 1:17
    do the recursive call, we have to create a new string, and
  • 1:17 - 1:20
    that's pretty expensive. Another reason is that the recursive calls
  • 1:20 - 1:24
    themselves are fairly expensive, and there are languages that make
  • 1:24 - 1:27
    recursive calls fairly cheap. Python is not one of them.
  • 1:27 - 1:31
    In Python, it's fairly expensive to do a recursive call. So
  • 1:31 - 1:34
    for most procedures, the recursive way is often the most
  • 1:34 - 1:37
    elegant, and the easiest way to get correct. If we're
  • 1:37 - 1:39
    really worried about performance, and we need procedures to work
  • 1:39 - 1:42
    on really large inputs. We're often better off trying to find
  • 1:42 - 1:45
    a non recursive way of defining that procedure.
タイトル:
Recursive Vs Iterative - Intro to Computer Science
概説:

more » « less
Video Language:
English
Team:
Udacity
プロジェクト:
CS101 - Intro to Computer Science
Duration:
01:47

English subtitles

改訂 Compare revisions