Recursion

information about SharpBASIC language elements
Post Reply
User avatar
frank
Site Admin
Posts: 40
Joined: Sun Nov 21, 2021 12:04 pm
Location: Netherlands
Contact:

Recursion

Post by frank »

SharpBASIC supports recursion for subroutines and functions. When using recursion, always keep in mind the following three basic rules:
  • A recursive algorithm must call itself, recursively.
  • A recursive algorithm must have a base case.
  • A recursive algorithm must change its state and move toward the base case.
A base case is the condition that allows the algorithm to stop recursing.

A base case is typically a problem that is small enough to solve directly. In the factorial algorithm the base case is n=1. We must arrange for a change of state that moves the algorithm toward the base case. A change of state means that some data that the algorithm is using is modified. Usually the data that represents our problem gets smaller in some way. In the factorial n decreases.

Example of recursive factorial and fibonacci:

Code: Select all

decl func factorial(n: int): int;
decl func fibonacci(n: int): int;

dim i, n: int;

main do

  n = 5;

  print("factorial of 5:");
  print(factorial(n));
  print();

  print("fibonacci of 5:");

  count i up 0 to n - 1 do
    print(fibonacci(i));
  end;

  print();

end;

func factorial(n: int): int
do
  if n == 0 do
    return 1;
  end;

  factorial = n * factorial(n - 1);
end;

func fibonacci(n: int): int
do
  when n is 0, 1 do
    return n;
  end;

  fibonacci = (fibonacci(n - 1) + fibonacci(n - 2));
end;
Output:

factorial of 5:
120

fibonacci of 5:
0
1
1
2
3
Keep it simple!
Post Reply