0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525  深究递归和迭代的区别、优缺点及实例对比 - 日记屋
深究递归和迭代的区别、优缺点及实例对比
发布时间:

1.迭代是人,递归是神!

从“编程之美”的角度看,可以借用一句非常经典的话:“迭代是人,递归是神!”来从宏观上对二者进行把握。

从概念上讲,递归就是指程序调用自身的编程思想,即一个函数调用本身;迭代是利用已知的变量值,根据递推公式不断演进得到变量新值得编程思想。

2.递归

递归就是函数自己调用自己。

2.1构成递归需具备的条件:

  1. 子问题须与原始问题为同样的事,且更为简单;

2. 不能无限制地调用本身,须有个出口,化简为非递归状况处理。

2.2递归的基本原理

第一:每一级的函数调用都有自己的变量。

第二:每一次函数调用都会有一次返回。

第三:递归函数中,位于递归调用前的语句和各级被调用函数具有相同的执行顺序。

第四:递归函数中,位于递归调用后的语句的执行顺序和各个被调用函数的顺序相反。

第五:虽然每一级递归都有自己的变量,但是函数代码并不会得到复制。

2.3递归优缺点

深究递归和迭代的区别、优缺点及实例对比

2.4编写一个递归函数

  • 这个递归函数的功能是什么,怎样调用这个函数,即设计好递归函数的返回值和参数列表

  • 什么时候应该结束这个递归,它的边界条件(出口)是什么(边界条件)

  • 在非边界情况时,怎样从第n层转变成第n+1层(递推公式)

例:

int f(int n) {
  //出口
    if (n > 0) {
        return n + f(n - 1);
    } else {
        return 0;
    }
}

解析:

深究递归和迭代的区别、优缺点及实例对比

 具体步骤:

深究递归和迭代的区别、优缺点及实例对比

递归递归,有递就得有归(出口),只递不归会导致程序崩溃。

要得到n - 1的积直接调用 f(x) 这个函数就行了,完全不需要思考这个函数怎么执行的。

3.例题:走楼梯

3.1题目描述:

一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。求总共有多少总跳法。I第一行输入T,表示有多少个测试数据。接下来T行,每行输入一个数n,表示台阶的阶数。
输出时每一行对应一个输出。

假如一共有三级台阶,一共有多少种走法?

深究递归和迭代的区别、优缺点及实例对比

假设有n级台阶,一共有多少种走法?

深究递归和迭代的区别、优缺点及实例对比

当n > 2 时,如果走1级有多少种走法 + 如果走2级有多少种走法,就是n级台阶所有的走法。

4.求n!递归法

int fun(int n) {
    if (n == 1) {
        return 1;
    } else {
        return n * fun(n - 1);
    }
}

5.求n!迭代法

int fun(int n) {
    int x = 1;
    for (int i = 2; i <= n; i++) {
        x *= i;
    }
    return x;
}

6.迭代

  迭代与普通循环的区别是:迭代时,循环代码中参与运算的变量同时是保存结果的变量,当前保存的结果作为下一次循环计算的初始值。

  递归与普通循环的区别是:循环是有去无回,而递归则是有去有回(因为存在终止条件)。

  在循环的次数较大的时候,迭代的效率明显高于递归。

6.1现实中的迭代

  迭代的方式有所不同,假如有个产品要求6个月交货,我在第一个月就会拿出一个产品来,当然,这个产品会很不完善,会有很多功能还没有添加进去,bug很多,还不稳定,但客户看了以后,会提出更详细的修改意见,这样,你就知道自己距离客户的需求有多远,我回家以后,再花一个月,在上个月所作的需求分析、框架设计、代码、测试等等的基础上,进一步改进,又拿出一个更完善的产品来,给客户看,让他们提意见。
就这样,我的产品在功能上、质量上都能够逐渐逼近客户的要求,不会出现我花了大量心血后,直到最后发布之时才发现根本不是客户要的东西的情况。

6.2优势

这个过程也很像打游戏,你刚开始玩,一下子就输了,但是随着你玩的次数越来越多,你的技艺就越来越精湛,而这个结果,不是你在开始玩游戏的时候,规划出来的,而是在你玩的过程中,通过不断的输不断的输,练出来的。

所以,你能达成的结果,都是在你做的过程中,不断试错,不断调整,不断精进,最后自然而然得到的一个结果。

所以,我们不能把迭代简单的理解为“升级”。

升级,更多描述的是一个结果,是一种直接的,一次性的,达成的一个目标,是一种线性的进程。

而迭代,是通过无数次,不断的,重复的,接近一个目标,折返接近,再折返再接近,最终达到目标。它不是一次性完成的,是通过不断重复的,但每次重复又比之前更好一点,这样一种非线性的进程。

现在我们把“迭代”的关键词拆解一下:

1.重复:

不断的重复做,而不是一次性的完成。

2.改进

在做的过程中不断的改进、调整、优化。

3.认知升级

迭代的过程就是不断提高认知的过程,升级只是这个过程的一个结果。

本周热门