Author Topic: Recursion  (Read 13525 times)

0 Members and 1 Guest are viewing this topic.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Recursion
« Reply #45 on: November 04, 2021, 01:53:50 pm »
@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.

Offline TempodiBasic

  • Forum Resident
  • Posts: 1792
    • View Profile
Re: Recursion
« Reply #46 on: November 04, 2021, 08:07:28 pm »
Quote
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. Print "--------------------------------------"
  7. index = StartIndex
  8. PrintSquare index, stepperIndex, DoneIndex
  9.  
  10. ' can be done recursively with much caution to control the effect
  11. Sub PrintSquare (index, stepper, indexDone)
  12.     If index > indexDone Then Exit Sub
  13.     Print index ^ 2;
  14.     _Delay .1
  15.     If index = 18 Then stepper = -2  '<-----------------------newline
  16.     PrintSquare index + stepper, stepper, indexDone
  17.  
  18.  
Programming isn't difficult, only it's  consuming time and coffee

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Recursion
« Reply #47 on: November 04, 2021, 08:43:28 pm »
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.  

Offline Dimster

  • Forum Resident
  • Posts: 500
    • View Profile
Re: Recursion
« Reply #48 on: November 05, 2021, 09:55:17 am »
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. 

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Recursion
« Reply #49 on: November 05, 2021, 06:24:17 pm »
@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.     Input "enter a, b or 0 to quit "; a, b
  7.     If a <> 0 And b <> 0 Then Print GCD(a, b) Else End
  8.  
  9.     If b = 0 Then GCD = a Else GCD = GCD(b, a Mod b)
  10.  

Offline TempodiBasic

  • Forum Resident
  • Posts: 1792
    • View Profile
Re: Recursion
« Reply #50 on: November 05, 2021, 10:59:29 pm »
@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.  
  9. Print "another try: the variable a grows up to 100 step 10 until"
  10. Print " it becomes 50, after this variable a should decrease step -10"
  11. a = 1: b = 100: c = 10
  12. For a = 1 To b Step c
  13.     Print a; " ";
  14.     If a = 50 Then c = -c
  15.  


@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.     choice$ = ""
  6.     Print " calculation of compound interest of a capital"
  7.     Print " please type amount of money, annual rate (rate for year), years of investment>"
  8.     Input "", money!, AnnRate!, Years%
  9.     Print CompoundInterest_loop
  10.     Print compoundInterest_Recursive(money!, AnnRate!, Years%)
  11.     Print "    press Spacebar to end, another key to replay"
  12.     Do While choice$ = ""
  13.         choice$ = InKey$
  14.     Loop
  15. Loop Until choice$ = " "
  16.  
  17. Function CompoundInterest_loop
  18.     Shared money!, AnnRate!, Years%
  19.     newmoney! = money! ' we use a local variable to not modify main variable MONEY!
  20.     For year = 1 To Years% Step 1
  21.         newmoney! = newmoney! + (newmoney! * AnnRate! / 100)
  22.     Next
  23.     CompoundInterest_loop = newmoney!
  24.  
  25. Function compoundInterest_Recursive (newmoney!, Rate!, ActYears%)
  26.     compoundInterest_Recursive = newmoney! ' <------------- this save last result
  27.     If ActYears% = 0 Then Exit Function
  28.     Themoney! = newmoney! + ((newmoney! * Rate!) / 100)
  29.     ActYears% = ActYears% - 1
  30.     money! = compoundInterest_Recursive(Themoney!, Rate!, ActYears%)
  31.     compoundInterest_Recursive = money!

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

@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.



Programming isn't difficult, only it's  consuming time and coffee

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Recursion
« Reply #51 on: November 05, 2021, 11:51:02 pm »
Quote
@bplus @Dimster
what do you think about the FOR STEP NEXT glitch pointed out by my example?

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

Offline Dimster

  • Forum Resident
  • Posts: 500
    • View Profile
Re: Recursion
« Reply #52 on: November 06, 2021, 10:32:00 am »
@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??

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Recursion
« Reply #53 on: November 06, 2021, 11:00:09 am »
Quote
@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.     If b = 0 Then GCD = a Else GCD = GCD(b, a Mod b)
  2.  
  3. '' Else GCD = GCD(b, a Mod b)" that's a call to itself.
  4.  

Quote
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.
« Last Edit: November 06, 2021, 11:17:34 am by bplus »

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Recursion
« Reply #54 on: November 06, 2021, 11:44:29 am »
@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.     choice$ = ""
  6.     ' bplus changed wording of next 3 lines
  7.     Print " Calculation of Compound (Yearly) Interest of a Principle Deposit."
  8.     Print " Please type: (don't forget commas between numbers)"
  9.     Print " Principle amount of money, Annual Rate Percent, 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.  
  19. Function CompoundInterest_loop
  20.     Shared money!, AnnRate!, Years% ' bplus comments nice! unfamiliar with this use of Shared
  21.     newmoney! = money! ' we use a local variable to not modify main variable MONEY!
  22.     For year = 1 To Years% Step 1
  23.         newmoney! = newmoney! + (newmoney! * AnnRate! / 100)
  24.     Next
  25.     CompoundInterest_loop = newmoney!
  26.  
  27. 'Function compoundInterest_Recursive (newmoney!, Rate!, ActYears%)
  28. '    compoundInterest_Recursive = newmoney! ' <------------- this save last result  ??? do we need this ???
  29. '    If ActYears% = 0 Then Exit Function
  30. '    Themoney! = newmoney! + ((newmoney! * Rate!) / 100)
  31. '    ActYears% = ActYears% - 1
  32. '    money! = compoundInterest_Recursive(Themoney!, Rate!, ActYears%) ' ??? do we need this ???
  33. '    compoundInterest_Recursive = money!
  34. 'End Function
  35.  
  36. ' bplus tries some line removals
  37. Function compoundInterest_Recursive (newmoney!, Rate!, ActYears%)
  38.     If ActYears% = 0 Then compoundInterest_Recursive = newmoney!: Exit Function
  39.     compoundInterest_Recursive = compoundInterest_Recursive(newmoney! + ((newmoney! * Rate!) / 100), Rate!, ActYears% - 1)
  40.  
  41.  
  42.  
« Last Edit: November 06, 2021, 11:50:56 am by bplus »

Offline Dimster

  • Forum Resident
  • Posts: 500
    • View Profile
Re: Recursion
« Reply #55 on: November 06, 2021, 01:43:38 pm »
I see it now @bplus - said the blind man as he picked up his hammer and saw.

FellippeHeitor

  • Guest
Re: Recursion
« Reply #56 on: November 06, 2021, 04:23:18 pm »
@TempodiBasic hi Tempo. Regarding:

Quote
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.

Offline TempodiBasic

  • Forum Resident
  • Posts: 1792
    • View Profile
Re: Recursion
« Reply #57 on: November 06, 2021, 10:53:34 pm »
@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
Programming isn't difficult, only it's  consuming time and coffee

FellippeHeitor

  • Guest
Re: Recursion
« Reply #58 on: November 07, 2021, 12:17:41 am »
@TempodiBasic yeah, you can't do that. There are no plans for now to implement that either.