在递归过程中究竟发生了什么？

Question

谁能告诉我递归程序到底发生了什么？??

Answer 1

函数会反复调用自身,直到满足某些条件.

一个愚蠢的例子:如何递归地走100步:

 function walk(steps) {
     if (steps > 0) { // not there yet
        take 1 step
        walk(steps - 1); // we're 1 step closer, now walk the rest of the way
     } else { // we're there already, don't walk any further than requested
        echo "You're there!"
     }
 }

 walk(100); // go!

这是发生的事情:

 walk(100):
   take 1 step
   walk(99):
     take 1 step
     walk(98):
       take 1 step
       walk(97):
         (...)
                   walk(2):
                     take 1 step
                     walk(1):
                       take 1 step
                       walk(0):
                         // "steps > 0" no longer true, use the "else" branch
                         echo "You're there!"

请注意,使用循环("迭代")可以实现相同的功能:

function walk(steps) {
  for (c=steps; c > 0; c--) { // note the condition check - "c > 0"
    take 1 step
  }
  echo "You're there!"
}

walk(100); // go!

程序流程会有所不同,但结果是一样的:

walk(100):
  c=100
  take 1 step
  c=99
  take 1 step
  c=98
  take 1 step
  (...)
  c=2
  take 1 step
  c=1
  take 1 step
  c=0
  // "c > 0" no longer true, exit loop
  echo "You're there!"

不能说递归或迭代总是更好.在这个例子中,迭代(循环)比递归更容易编写和更容易理解; 在其他情况下(例如遍历树结构),递归可能是更好的解决方案.