## 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
 Udacity Robot edited 英語(米国) subtitles for 22-17 Recursive Vs Iterative Udacity Robot edited 英語(米国) subtitles for 22-17 Recursive Vs Iterative Udacity Robot edited 英語(米国) subtitles for 22-17 Recursive Vs Iterative Udacity Robot edited 英語(米国) subtitles for 22-17 Recursive Vs Iterative Udacity Robot edited 英語(米国) subtitles for 22-17 Recursive Vs Iterative Cogi-Admin edited 英語(米国) subtitles for 22-17 Recursive Vs Iterative

# English subtitles

## 改訂 Compare revisions

• API
Udacity Robot
• API
Udacity Robot
• API
Udacity Robot
• API
Udacity Robot
• API
Udacity Robot
• API