15 / 16

Recursive Functions

Functions can call functions. We saw that, the main function called the square function. But what if you have a function fun that calls fun!? That is right, it is possible and useful sometimes.

Let's write a recursive function that counts down from n to 0.
Steps:

  • add a new function countdown()
  • add a new parameter n: Integer
  • add a new If block with condition x > 0
  • output n in the true branch
  • call countdown(n-1) after it
  • call countdown(5) in the main

Run the program, it should display 5, 4, 3, 2, 1 in the output.
So, how does this magic work? When countdown is called with argument 5 it prints it.
Then it calls itself (recursively) with a different argument n-1 which is in this case 4. Then that invocation calls itself with 3 etc.

The most important part is that the recursion eventually stops. The base case or termination condition in this case is the false branch. Recursion must finish somehow. This is the same case as with loops! If the number reaches 0, nothing will happen, and recursion ends there.

Note that you will probably need some time to chew on this concept, so no worries if it "doesn't click" immediately. Debugger is your friend here, so use it!