A graphical presentation of recursion as a divide-and-conquer technique  

  • How recursion is used as a divide-and-conquer technique illustrated:

    Original problem:   compute factorial(10) (= 10!)

  A graphical presentation of recursion as a divide-and-conquer technique  

  • Divide:   can I use solution(s) of smaller factorial(s) to solve 10! ?

    Answer:   yes, we can use factorial(9) (= 9!)

  A graphical presentation of recursion as a divide-and-conquer technique  

  • Divide:   let/delegate someone else (helper) to solve 9!:

    Important:   you need to trust that this helper will return the correct solution

  A graphical presentation of recursion as a divide-and-conquer technique  

  • Divide:   after delegating the helper to solve 9!, you wait for the answer/solution:

    Important:   you need to trust that this helper will return the correct solution

  A graphical presentation of recursion as a divide-and-conquer technique  

  • Divide:   the helper returns the answer for 9! to you:

    Next:   you still need to use the answer to solve the original problem...

  A graphical presentation of recursion as a divide-and-conquer technique  

  • Conquer:   you solve the original problem 10! using 362880 (which is the answer for 9!)

    So you and helper are 2 different "entities"/ method calls that collaborate to solve 10!