understanding basic recursion

by

Imagine you are the computer, and someone hands you a paper with

factorial(3)

written on it. You then execute the procedure, looking at the argument. Since it’s > 1, you write 

factorial(2)

on another piece of paper and “hand it to yourself”, waiting until you get the answer to that one before proceeding.

Again you execute the procedure. Since 2 is still > 1 you write

factorial(1)

on yet another piece of paper and hand it to yourself, waiting until you get the answer to this one before proceeding.

Again, you execute the procedure. This time the input is 1, so you take the first branch and return 1. The invocation that was processing factorial(2) now has an answer so it multiplies 2 by that answer (1) and returns. Now the invocation that was handling factorial(3) gets its answer (2) and multiplies it by 3, giving 6. It then returns that answer to the person who started the whole operation.

If you imagine that you kept the pieces of paper in a stack in front of you as you were working, that is a visualization of the “stack” in the computer’s memory. Each recursive invocation stores the parameter (and any temporary variables) on its own piece of paper (stack frame) literally arranged as a pushdown stack just like the papers, one on top of the other.

More Related Contents:

  1. Java simple recursive function explanation [closed]
  2. Why isn't this work? String value won't change. Recursion [closed]
  3. how to change code this into recursion Java? [closed]
  4. Recursive method for 2,4,8,..in java [closed]
  5. Operations on Strings
  6. Create lambda function which calculates factorial recursively
  7. Recursively list files in Java
  8. Why is the max recursion depth I can reach non-deterministic?
  9. Reversing a linked list in Java, recursively
  10. Java recursive Fibonacci sequence
  11. Reversing a String with Recursion in Java
  12. Factorial using Recursion in Java
  13. Whats the best way to recursively reverse a string in Java?
  14. Is there any way to do n-level nested loops in Java?
  15. Why does the count of calls of a recursive method causing a StackOverflowError vary between program runs? [duplicate]
  16. Recursive ConcurrentHashMap.computeIfAbsent() call never terminates. Bug or “feature”?
  17. The difference between head & tail recursion [duplicate]
  18. Recursive Fibonacci memoization
  19. Finding Max value in an array using recursion
  20. How does recursion work? [closed]
  21. Implement recursive lambda function using Java 8
  22. Tail Call Optimisation in Java
  23. The easiest way to remove the bidirectional recursive relationships?
  24. How to flatten all items from a nested Java Collection into a single List?
  25. Breaking out of a recursion in java
  26. Counting nodes in a tree in Java
  27. HQL recursion, how do I do this?
  28. java.lang.StackOverflowError due to recursion
  29. How to deep copy a Binary Tree?
  30. Recursion in JSF (c:forEach vs. ui:repeat)

Leave a Comment