Recursion

[bplus]

@Dimster

I hope you practice a little with recursive routines before attempting something serious ie with filed data.
They are simple, elegant usually, but they can be tricky to get working.

If you can replace a Recursive subroutine with a simple loop that would very likely be a better way to go.

[TempodiBasic]

A recursive routine can act as a loop

Yes a loop in which you take track of previouse value and actions done in the recursive block!
It becames too mad when you call the sub at the middle of itself, leaving undone the second part of the SUB/FUNCTION

see here what difference with the little addition of a line of code to the 2nd example of Bplus

Code: QB64: [Select]

1. StartIndex = 2: stepperIndex = 2: DoneIndex = 20
2. For index = StartIndex To DoneIndex Step stepperIndex
3.     Print index ^ 2;
4.     _Delay .1
5.     If index = 18 Then stepperIndex = -2  '<------------------------newline
6. Next
7. Print "--------------------------------------"
8. index = StartIndex
9. PrintSquare index, stepperIndex, DoneIndex
10.  
11. ' can be done recursively with much caution to control the effect
12. Sub PrintSquare (index, stepper, indexDone)
13.     If index > indexDone Then Exit Sub
14.     Print index ^ 2;
15.     _Delay .1
16.     If index = 18 Then stepper = -2  '<-----------------------newline
17.     PrintSquare index + stepper, stepper, indexDone
18. End Sub
19.  
20.  

[bplus]

see here what difference with the little subtraction in a line of code to the 1st example of Bplus mod by TempodiBasic

Code: QB64: [Select]

1. StartIndex = 2: stepperIndex = 2: DoneIndex = 20
2. For index = StartIndex To DoneIndex Step stepperIndex
3.     Print index ^ 2;
4.     _Delay .1
5.     If index = 18 Then index = -2 '<------------------------newline
6. Next
7.  

[Dimster]

Good advice @bplus . I am interested in improving the speed of some of my looping routines in the main program code. I'm hoping to see a difference in speed from the iteration of a loop in the main program to recursion in a sub/function. Iteration and recursion seem to mean the same thing to me but as I'm looking at my code the iteration of looping seems more cumbersome (less elegant to use your observation) than recursive coding. But as  you say, I'll "practice a little" with it and see if I can achieve either better accuracy or improved speed with recursion. Truth be told, can't hurt to learn recursion.

@TempodiBasic ... I gather the line you added has the effect of not only creating an infinite loop but also a demonstration that the loop will never overload the stack. But is the bigger point you are making that once recursion is used, you can stop it's run and restart from where it left off whereas Looping, once stopped, needs to restart from the beginning?? Sorry if I misunderstood. 

[bplus]

@Dimster

Here's another nice one for your collection:

Code: QB64: [Select]

1. _Title "GCD by Recursion" 'b+ 2021-11-05
2. ' In mathematics GCD or Greatest Common Divisor of two or more integers
3. ' is the largest positive integer that divides both the number
4. ' without leaving any remainder.
5.  
6. While 1
7.     Input "enter a, b or 0 to quit "; a, b
8.     If a <> 0 And b <> 0 Then Print GCD(a, b) Else End
9. Wend
10.  
11. Function GCD (a As _Integer64, b As _Integer64)
12.     If b = 0 Then GCD = a Else GCD = GCD(b, a Mod b)
13. End Function
14.  

[TempodiBasic]

@bplus
fine as you have make a pendulum (infinite palindrome generator) of digit sequence!
It is very interesting and fine! The power of 2 is very strong!

--------
@bplus @Dimster
what do you think about the FOR STEP NEXT glitch pointed out by my example?

Code: QB64: [Select]

1. StartIndex = 2: stepperIndex = 2: DoneIndex = 20
2. Print "StepperIndex is 2 but when index will be 18 it becomes -2"
3. Print " so we expect to see index to decrement after 18 towards negative digits"
4. For index = StartIndex To DoneIndex Step stepperIndex
5.     Print index; "->"; index ^ 2;
6.     _Delay .1
7.     If index = 18 Then stepperIndex = -2 '<------------------------newline
8. Next
9.  
10. Print
11. Print "another try: the variable a grows up to 100 step 10 until"
12. Print " it becomes 50, after this variable a should decrease step -10"
13. a = 1: b = 100: c = 10
14. For a = 1 To b Step c
15.     Print a; " ";
16.     If a = 50 Then c = -c
17. Next
18.  

@Dimster
yes you are very near to original sight of my communication
Loop and recursion can be very similar but often a change made into a loop make a very different effect if it is made in a recursion loop.
This is more true when the recursive loop call itself in the middle of sub/function recursive because the rest part of recursive has not been already executed. So you cannot have a more specific control on this part of recursion in the meaning that you cannot know what recursion bring back as true as you cannot know how times the recursion will be called on fly.
From this comes out that you say in your affimation: if you stop a recursion the data in all the sub called are still available, while in the loop you can access only to the data of the current cycle of loop.
But yes recursion is fine, beautyful, elegant and more exciting versus loop when it is possible, you must only pay more attention for details.
see this financial example

Code: QB64: [Select]

1. $Debug
2. 'recursion versus loop
3. ' calcularion of compound interest of a capital in years of investment
4. ' here a definition: https://en.wikipedia.org/wiki/Future_value#Compound_interest
5. Cls
6. Do
7.     choice$ = ""
8.     Print " calculation of compound interest of a capital"
9.     Print " please type amount of money, annual rate (rate for year), years of investment>"
10.     Input "", money!, AnnRate!, Years%
11.     Print CompoundInterest_loop
12.     Print compoundInterest_Recursive(money!, AnnRate!, Years%)
13.     Print "    press Spacebar to end, another key to replay"
14.     Do While choice$ = ""
15.         choice$ = InKey$
16.     Loop
17. Loop Until choice$ = " "
18. End
19.  
20. Function CompoundInterest_loop
21.     Shared money!, AnnRate!, Years%
22.     newmoney! = money! ' we use a local variable to not modify main variable MONEY!
23.     For year = 1 To Years% Step 1
24.         newmoney! = newmoney! + (newmoney! * AnnRate! / 100)
25.     Next
26.     CompoundInterest_loop = newmoney!
27. End Function
28.  
29. Function compoundInterest_Recursive (newmoney!, Rate!, ActYears%)
30.     compoundInterest_Recursive = newmoney! ' <------------- this save last result
31.     If ActYears% = 0 Then Exit Function
32.     Themoney! = newmoney! + ((newmoney! * Rate!) / 100)
33.     ActYears% = ActYears% - 1
34.     money! = compoundInterest_Recursive(Themoney!, Rate!, ActYears%)
35.     compoundInterest_Recursive = money!
36. End Function

-----------------------------------------------

@FellippeHeitor  and @QB64 Developers Team

nice to do some sessions of debug.
I find this new feature very powerful.
Waiting when I can observe array variable with variable index.
Thanks for your efforts.

[bplus]

@bplus @Dimster
what do you think about the FOR STEP NEXT glitch pointed out by my example?

Code: QB64: [Select]

1. Print
2. Print "another try: the variable a grows up to 100 step 10 until"
3. Print " it becomes 50, after this variable a should decrease step -10"
4. a = 1: b = 100: c = 10
5. For a = 1 To b Step c
6.     Print a; " ";
7.     If a = 50 Then c = -c ' <<<<<<<<<<<<< a never = 50 so c never changed!
8. Next
9. Print: Print "c ="; c
10.  
11. Print "another try: the variable a grows up to 100 step 10 until"
12. Print " it becomes 50, after this variable a should decrease step -10"
13. a = 1: b = 100: c = 10
14. For a = 1 To b Step c
15.     Print a; " ";
16.     If a = 51 Then c = -c 'fixed but in For loop b, c changes aren't acknowledged until after loop
17. Next
18. Print: Print "c ="; c
19.  
20. Print "another try: the variable a grows up to 10 step 1 until"
21. Print " it becomes 5, after this variable a should decrease step -1"
22. a = 1: b = 10: c = 1
23. For a = 1 To b Step c
24.     c = c + 1 ' change c into counter
25.     Print a; " ";
26.     If a = 5 Then b = 9 ' !!!! For loop b, c changes aren't acknowledged until after loop
27.     If b = 9 Then a = a - 2
28.     If a = 0 Then b = 0 ' So we exploit that and make "palindromic pendulum"
29.     _Delay .5
30. Next
31. Print: Print "c ="; c
32.  
33.  

[Dimster]

@TempodiBasic - thanks for that Compound Interest routine. It's a handy little item especially for a person like myself who follows the stock market.

@bplus - GCD has potential application in some of the data crunching I'm working with, thanks for same. The question I have on that routine is , How would it meet the definition of Recursion as we have been discussing here? I understand Recursion is a sub/function which calls itself but there does not appear to be a specific call to itself in the GCD code.

On the matter of the negative stepping. Originally it struck me that the iterations could never reach the DoneIndex @ 20, making it an endless loop. I totally missed the bigger picture of the mis-stepping when the negative stepping kicked in.  Some very good lessons here.

One other question @bplus - I notice you initialized the variables before each looping. Is there an advantage to this or just because there were multiple values in "a" prior to the looping? Especially when variable "a" which gets its values in the For statement so the prior values should be overwritten??

[bplus]

@bplus - GCD has potential application in some of the data crunching I'm working with, thanks for same. The question I have on that routine is , How would it meet the definition of Recursion as we have been discussing here? I understand Recursion is a sub/function which calls itself but there does not appear to be a specific call to itself in the GCD code.

but GCD is calling itself, look again:

Code: QB64: [Select]

1. Function GCD (a As _Integer64, b As _Integer64)
2.     If b = 0 Then GCD = a Else GCD = GCD(b, a Mod b)
3. End Function
4.  
5. '' Else GCD = GCD(b, a Mod b)" that's a call to itself.
6.  

One other question @bplus - I notice you initialized the variables before each looping. Is there an advantage to this or just because there were multiple values in "a" prior to the looping? Especially when variable "a" which gets its values in the For statement so the prior values should be overwritten??

Oh the a = 1, that's just lazy copy/paste, you are right a = 1 was waste of space because a is reset in For loop.

[bplus]

@TempodiBasic

+1 agreed that is a handy calculation.

I have made a couple of mods to maybe clear up wording and show elegance of recursive function:

Code: QB64: [Select]

1. ' bplus mod of TempodiBasic 2021-11-06
2. 'recursion versus loop
3. ' calcularion of compound interest of a capital in years of investment
4. ' here a definition: https://en.wikipedia.org/wiki/Future_value#Compound_interest
5. Cls
6. Do
7.     choice$ = ""
8.     ' bplus changed wording of next 3 lines
9.     Print " Calculation of Compound (Yearly) Interest of a Principle Deposit."
10.     Print " Please type: (don't forget commas between numbers)"
11.     Print " Principle amount of money, Annual Rate Percent, Years of investment"
12.     Input "", money!, AnnRate!, Years%
13.     Print CompoundInterest_loop
14.     Print compoundInterest_Recursive(money!, AnnRate!, Years%)
15.     Print "    press Spacebar to end, another key to replay"
16.     Do While choice$ = ""
17.         choice$ = InKey$
18.     Loop
19. Loop Until choice$ = " "
20. End
21.  
22. Function CompoundInterest_loop
23.     Shared money!, AnnRate!, Years% ' bplus comments nice! unfamiliar with this use of Shared
24.     newmoney! = money! ' we use a local variable to not modify main variable MONEY!
25.     For year = 1 To Years% Step 1
26.         newmoney! = newmoney! + (newmoney! * AnnRate! / 100)
27.     Next
28.     CompoundInterest_loop = newmoney!
29. End Function
30.  
31. 'Function compoundInterest_Recursive (newmoney!, Rate!, ActYears%)
32. '    compoundInterest_Recursive = newmoney! ' <------------- this save last result  ??? do we need this ???
33. '    If ActYears% = 0 Then Exit Function
34. '    Themoney! = newmoney! + ((newmoney! * Rate!) / 100)
35. '    ActYears% = ActYears% - 1
36. '    money! = compoundInterest_Recursive(Themoney!, Rate!, ActYears%) ' ??? do we need this ???
37. '    compoundInterest_Recursive = money!
38. 'End Function
39.  
40. ' bplus tries some line removals
41. Function compoundInterest_Recursive (newmoney!, Rate!, ActYears%)
42.     If ActYears% = 0 Then compoundInterest_Recursive = newmoney!: Exit Function
43.     compoundInterest_Recursive = compoundInterest_Recursive(newmoney! + ((newmoney! * Rate!) / 100), Rate!, ActYears% - 1)
44. End Function
45.  
46.  
47.  

[Dimster]

I see it now @bplus - said the blind man as he picked up his hammer and saw.

[FellippeHeitor]

@TempodiBasic hi Tempo. Regarding:

Waiting when I can observe array variable with variable index

That's already a feature. When you double click an array in the Variable List, you will be asked which indexes you want to watch.

[TempodiBasic]

@bplus
Hi, I like your beautify of recursive function. Very good!

@Dimster
I'm happy that I can give a positive spin to your curiosity and interest about recursion method of programming

@FellippeHeitor
Hi,
maybe that I have misunderstood how to watch into arrays. I'll watch again your video on youtube.
For now I have understood (wrongly) that I can observe a(1) or a(19) of A(1 to 20) but not a(b%) also in the specific
row of code in which b% has its clear value.
Thanks

[FellippeHeitor]

@TempodiBasic yeah, you can't do that. There are no plans for now to implement that either.