Prashnikaप्रश्निका
Code
About

Recursion visualiser

See what recursion really does. Pick a method and a number, then press Play: each call goes on the call stack, the calls branch out into a tree down to the base case, and the answers come back up one by one, with the Java line that is running lit all the way.

How to use it

  1. 1Pick a method (factorial, Fibonacci, power, GCD or sum of digits) and type a number, or tap an example.
  2. 2Press Show me, then Play. Use Back and Next, the slider or the arrow keys to go through it at your own speed.
  3. 3Watch the call tree grow, the call stack fill and empty, and the Java line that is running.
Not sure what to type? Tap an example:
factorial of 4factorial of 20: a deep stackFibonacci of 5: the tree branches2 to the power 6GCD of 48 and 18sum of the digits of 1234
Which method

The ranges keep each run small. Factorial: 0 to 20. Fibonacci: 0 to 7. Power: base 1 to 20, exponent 0 to 10. GCD: both numbers 1 to 99999. Sum of digits: 0 to 999999999.

The animation needs JavaScript. Every step is written out below.

Result

Result
fact(20) = 2432902008176640000
Every step in words (60 steps)
  1. fact(20) is called, so its frame goes on the call stack.
  2. n = 20. Is n <= 1? No, so it needs fact(19) first.
  3. fact(20) calls fact(19) and waits for its answer.
  4. n = 19. Is n <= 1? No, so it needs fact(18) first.
  5. fact(19) calls fact(18) and waits for its answer.
  6. n = 18. Is n <= 1? No, so it needs fact(17) first.
  7. fact(18) calls fact(17) and waits for its answer.
  8. n = 17. Is n <= 1? No, so it needs fact(16) first.
  9. fact(17) calls fact(16) and waits for its answer.
  10. n = 16. Is n <= 1? No, so it needs fact(15) first.
  11. fact(16) calls fact(15) and waits for its answer.
  12. n = 15. Is n <= 1? No, so it needs fact(14) first.
  13. fact(15) calls fact(14) and waits for its answer.
  14. n = 14. Is n <= 1? No, so it needs fact(13) first.
  15. fact(14) calls fact(13) and waits for its answer.
  16. n = 13. Is n <= 1? No, so it needs fact(12) first.
  17. fact(13) calls fact(12) and waits for its answer.
  18. n = 12. Is n <= 1? No, so it needs fact(11) first.
  19. fact(12) calls fact(11) and waits for its answer.
  20. n = 11. Is n <= 1? No, so it needs fact(10) first.
  21. fact(11) calls fact(10) and waits for its answer.
  22. n = 10. Is n <= 1? No, so it needs fact(9) first.
  23. fact(10) calls fact(9) and waits for its answer.
  24. n = 9. Is n <= 1? No, so it needs fact(8) first.
  25. fact(9) calls fact(8) and waits for its answer.
  26. n = 8. Is n <= 1? No, so it needs fact(7) first.
  27. fact(8) calls fact(7) and waits for its answer.
  28. n = 7. Is n <= 1? No, so it needs fact(6) first.
  29. fact(7) calls fact(6) and waits for its answer.
  30. n = 6. Is n <= 1? No, so it needs fact(5) first.
  31. fact(6) calls fact(5) and waits for its answer.
  32. n = 5. Is n <= 1? No, so it needs fact(4) first.
  33. fact(5) calls fact(4) and waits for its answer.
  34. n = 4. Is n <= 1? No, so it needs fact(3) first.
  35. fact(4) calls fact(3) and waits for its answer.
  36. n = 3. Is n <= 1? No, so it needs fact(2) first.
  37. fact(3) calls fact(2) and waits for its answer.
  38. n = 2. Is n <= 1? No, so it needs fact(1) first.
  39. fact(2) calls fact(1) and waits for its answer.
  40. n = 1. Is n <= 1? Yes, so this is the base case.
  41. Base case: it returns 1 straight away, with no further call.
  42. fact(1) came back with 1, so fact(2) works out 2 * 1 = 2 and returns it. Its frame leaves the stack.
  43. fact(2) came back with 2, so fact(3) works out 3 * 2 = 6 and returns it. Its frame leaves the stack.
  44. fact(3) came back with 6, so fact(4) works out 4 * 6 = 24 and returns it. Its frame leaves the stack.
  45. fact(4) came back with 24, so fact(5) works out 5 * 24 = 120 and returns it. Its frame leaves the stack.
  46. fact(5) came back with 120, so fact(6) works out 6 * 120 = 720 and returns it. Its frame leaves the stack.
  47. fact(6) came back with 720, so fact(7) works out 7 * 720 = 5040 and returns it. Its frame leaves the stack.
  48. fact(7) came back with 5040, so fact(8) works out 8 * 5040 = 40320 and returns it. Its frame leaves the stack.
  49. fact(8) came back with 40320, so fact(9) works out 9 * 40320 = 362880 and returns it. Its frame leaves the stack.
  50. fact(9) came back with 362880, so fact(10) works out 10 * 362880 = 3628800 and returns it. Its frame leaves the stack.
  51. fact(10) came back with 3628800, so fact(11) works out 11 * 3628800 = 39916800 and returns it. Its frame leaves the stack.
  52. fact(11) came back with 39916800, so fact(12) works out 12 * 39916800 = 479001600 and returns it. Its frame leaves the stack.
  53. fact(12) came back with 479001600, so fact(13) works out 13 * 479001600 = 6227020800 and returns it. Its frame leaves the stack.
  54. fact(13) came back with 6227020800, so fact(14) works out 14 * 6227020800 = 87178291200 and returns it. Its frame leaves the stack.
  55. fact(14) came back with 87178291200, so fact(15) works out 15 * 87178291200 = 1307674368000 and returns it. Its frame leaves the stack.
  56. fact(15) came back with 1307674368000, so fact(16) works out 16 * 1307674368000 = 20922789888000 and returns it. Its frame leaves the stack.
  57. fact(16) came back with 20922789888000, so fact(17) works out 17 * 20922789888000 = 355687428096000 and returns it. Its frame leaves the stack.
  58. fact(17) came back with 355687428096000, so fact(18) works out 18 * 355687428096000 = 6402373705728000 and returns it. Its frame leaves the stack.
  59. fact(18) came back with 6402373705728000, so fact(19) works out 19 * 6402373705728000 = 121645100408832000 and returns it. Its frame leaves the stack.
  60. fact(19) came back with 121645100408832000, so fact(20) works out 20 * 121645100408832000 = 2432902008176640000 and returns it. Its frame leaves the stack.
Start again

About the Recursion visualiser

What it does

Runs a recursive method for the number you give and replays it one step at a time. Every call appears in the call tree and goes on the call stack; when a call reaches the base case it returns its value, and each earlier call then finishes its own working and returns in turn. The Java line being run is marked, and a sentence says what just happened. It is the dry run that ISC Computer Science recursion questions ask you to write.

What you see

  • Call tree: one box for every call. A box with a bold outline is waiting for the calls below it; the filled box is the call being worked on; a box with an arrow and a value has returned.
  • Call stack: the calls that have started but not yet returned, newest on top. Its height is how deep the recursion is.
  • Code: the Java method, with the current line marked.

The ranges

To keep every run small the numbers are limited: factorial 0 to 20, Fibonacci 0 to 7, power with a base of 1 to 20 and an exponent of 0 to 10, GCD of two numbers from 1 to 99999, and sum of digits up to 9 digits.

Common questions

What is a base case?

The base case is the call that can be answered without calling the method again, for example n <= 1 in factorial. Every recursive method needs one, or the calls never stop and the program ends with a stack overflow.

What is the call stack in recursion?

It is the list of calls that have started but have not returned yet. Each call is added on top when it is made and removed when it returns, so the most recent call is always the one running. Watch it fill up on the way down to the base case and empty on the way back.

Why does the Fibonacci tree have so many calls?

Each call to fib(n) makes two more calls, and the same values are worked out again and again: fib(7) makes 41 calls in all. This is why this simple recursive method is slow for large n.

Why is factorial of 20 the largest?

20! is the largest factorial that fits in a Java long. The visualiser stops there, and the call stack for it is 20 calls deep.

Can I see the code in Python, JavaScript or C++?

Yes. Choose the language in the menu above the code. Only the listing changes: the steps are always worked out from the Java program that ISC uses, and the highlighted line moves to the matching line of the language you chose.

Practise on real ISC questions

More Computer Science tools

All study tools →