There is a recursion each time a word call itself into its defintion.

Some algorithms are smaller / cleaner with a recursion.

But the counterpart is that you need more space for the return stack as it will grow for each call (with at least the return address but also the word locals) until the condition that stops the recursion is reached.

For instance, to calculate the factorial of a number ( 1 * 2 * 3 ... * n ), you can write (without recursion) :

- Code: Select all
`: fact \ n -- n!`

| i |

1 swap loop: i [ i * ]

;

Or you can use a recursion, as you can write :

fact(0) = 1

fact(n) = fact(n-1) * n ( ie 1*2*3*... *n = n * 1*2*3*...*n-1 = n * fact(n-1) )

So :

- Code: Select all
`: fact ( n )`

n ifZero: [ 1 ] else: [ n 1- fact n * ]

;

When you call fact(5)

1) n = 5 so it pushes 5 on the stack, substrat 1 and call fact again.

2) n = 4 so it pushes 4 on the stack, substrat 1 and call fact again.

3) n = 3 so it pushes 3 on the stack, substrat 1 and call fact again.

4) n = 2 so it pushes 2 on the stack, substrat 1 and call fact again.

5) n = 1 so it pushes 1 on the stack, substrat 1 and call fact again.

6) n = 0 so it just pushes 1 on the stack and returns.

7) fact(1) pushes 1 (from RS) on the stack and call * ==> 1

8) fact(2) pushes 2 (from RS) on the stack and call * ==> 2

9) fact(3) pushes 3 (from RS) on the stack and call * ==> 6

10) fact(4) pushes 4 (from RS) on the stack and call * ==> 24

11) fact(5) pushes 5 (from RS) on the stack and call * ==> 120.

So you end with 120 on the stack ( ie fact(5) )

Franck